November Black Friday C# týden
BlackFriday je tu! Využij jedinečnou příležitost a získej až 80 % znalostí navíc zdarma! Více zde
Pouze tento týden sleva až 80 % na e-learning týkající se C#

Diskuze: Seřazení hodnot pro vývahu oběžného kola

Aktivity (4)
Avatar
mifro
Člen
Avatar
mifro:19. srpna 13:56

Ahoj, prosím o radu. Nevím, jak seřadit hodnoty, abych dosáhl co nejvíce symetrického paprskového grafu. Mám např. hmotnosti lopatek. 1=500g, 2=480g, 3=490g, 4=475g, 5=492g, 6=510g, 7=505g, 8=520g, 9=470g. Hmotnosti nyní potřebuji setřídit tak, abych po vložení paprskového grafu dostal co nejlepší tvar. Viz. příloha - příklad z excelu. Jedná se o co nejlepší vyvážení kola podle hmotnosti lopatek. Ručně to seřadím během chvilky, ale programově se nedokážu pohnout. Díky za každou radu.

 
Odpovědět
19. srpna 13:56
Avatar
Tomáš Valenta:19. srpna 15:41

Jsou ty hodnoty seřazené nějak speciálně nebo jde jen o to, aby se střídaly velké a malé hodnoty?

Nahoru Odpovědět
19. srpna 15:41
C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off.
Avatar
mifro
Člen
Avatar
Odpovídá na Tomáš Valenta
mifro:19. srpna 15:49

Jde o to, aby hodnoty byly co nejlépe rozděleny pro co nejlepší rozložení sil. Základ je, že nejtěžší lopatka půjde na 0°, druhá na 180°, třetí na 90° a čtvrtá na 270° (úhly jsou zde jen informativní a mohou se samozřejmě lišit podle počtu lopatek). Tzn. ideální stav je, že první 4 lopatky jdou do "kříže" a zbytek se rovnoměrně rozdělí mezi ně.

 
Nahoru Odpovědět
19. srpna 15:49
Avatar
STP
Člen
Avatar
Odpovídá na mifro
STP:19. srpna 22:31

Co znamená

a zbytek se rovnoměrně rozdělí mezi ně.

Něco takového pomůže? :)

static void Main(string[] args)
 {

     List<int> lopatky = new List<int> { 520, 510, 505, 500, 492, 490, 480, 475, 470 };

     List<int> lopatky0 = new List<int>();
     List<int> lopatky180 = new List<int>();
     List<int> lopatky90 = new List<int>();
     List<int> lopatky270 = new List<int>();

      lopatky = lopatky.OrderByDescending(i => i).ToList();

     for (int i = 0; i < lopatky.Count; i = i + 4)
     {
         lopatky0.Add(lopatky[i]);
         if (lopatky.Count > i + 1)
             lopatky180.Add(lopatky[i + 1]);
         if (lopatky.Count > i + 2)
             lopatky90.Add(lopatky[i + 2]);
         if (lopatky.Count > i + 3)
             lopatky270.Add(lopatky[i + 3]);

     }

     List<int> ret = new List<int>();
     ret.AddRange(lopatky0);
     ret.AddRange(lopatky90);
     ret.AddRange(lopatky180);
     ret.AddRange(lopatky270);

     foreach (var item in ret)
     {
         Console.WriteLine(item);
     }
     Console.ReadLine();
 }
Nahoru Odpovědět
19. srpna 22:31
Když umřít, tak online!!!
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:20. srpna 10:10

Jestli to spravne chapu, tak ty mas jakousi hvezdici z linek. Delka linek je v seznamu. Mas ty linie rozmistit tak, aby hvezdice byla, co nejvic kulata.

        o
        |
o-------+-----o
        |
        |
        o

Cili, kdyz body 'o' propojis mezi sebou, aby uhly byly co nejvetsi.
Natusim, ja bych postupoval projitim vsech moznosti.

 
Nahoru Odpovědět
20. srpna 10:10
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na mifro
Peter Mlich:20. srpna 10:14

" Ručně to seřadím během chvilky" - mozna by bylo dobre popsat postup, jak to delas rucne. Z toho plyne, jak napsat program. Takze bohuzel, to mas pro nas nahodne serazena cisla a netusim, jak vypada z htoho graf predtim a potom

 
Nahoru Odpovědět
20. srpna 10:14
Avatar
mifro
Člen
Avatar
Odpovídá na Peter Mlich
mifro:20. srpna 11:25

Ručně viz příloha. Prostě si přesouvám jednotlivé hmotnosti, až mi vznikne co nejlepší "kruh" tak, aby např. nejtěžší lopatky nebyly jen na jedné straně - aby hmotnost byla co nejlépe vyrovnaná.

 
Nahoru Odpovědět
20. srpna 11:25
Avatar
Odpovídá na STP
Andy Scheuchzer:20. srpna 11:53

Tohle by ještě chtělo se při každém druhém procházení cyklem posunout o 180°, ne?

Nahoru Odpovědět
20. srpna 11:53
Člověk, co si myslí, že snědl všechnu moudrost světa, i když tomu tak není.
Avatar
simon.steiner:20. srpna 12:42

Myslím, že cílem je dostat centrum hmostnosti všech lopatek co nejblíže středu, například pro zamezení vibrací v turbínách.

 
Nahoru Odpovědět
20. srpna 12:42
Avatar
mifro
Člen
Avatar
Odpovídá na STP
mifro:20. srpna 15:55

Díky, pomůže, jen to ještě není úplně ono, viz obrázek. Správně by mělo být 550 proti 530, pak otočit o 90° a 525 proti 505 a zybtek rovnoměrně mezi... Je to celkem oříšek...

 
Nahoru Odpovědět
20. srpna 15:55
Avatar
Tomáš Valenta:21. srpna 14:59

A jak se na to jde ručně? To zkoušíš prostě náhodně, dokud to nevypadá hezky nebo na to máš nějaký systém.

Nahoru Odpovědět
21. srpna 14:59
C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off.
Avatar
Mouser
Člen
Avatar
Odpovídá na mifro
Mouser:21. srpna 17:50

Zajímavá úloha. Já bych na to šel třeba tak, že bych lopatky seřadil od nejtěžší po nejlehčí, první dal na 0°, a zbylé postupně umisťoval doprostřed nejdelší zbývající "mezery". Tak to asi intuitivně dělá i člověk. Při více mezerách stejné délky vyberu tu s nejmenším součtem hmotností okolních lopatek.

Tady si můžeš vyzkoušet, jestli ti to vrací použitelné výsledky i pro jiné hodnoty.

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
        public static void Main()
        {
                int[] blades = { 500, 530, 550, 475, 450, 525, 460, 505 };
                foreach (int blade in SortBlades(blades)) Console.WriteLine(blade);
        }

        public static int[] SortBlades(int[] blades)
        {
                blades = blades.OrderByDescending(b => b).ToArray();

                int[] result = new int[blades.Length];
                if (result.Length == 0) return new int[0];
                result[0] = blades[0];

                for (int i = 1; i < blades.Length - 1; i++)
                {
                        // get the longest empty sequence and put the current blade to its middle index
                        var sequences = new List<Sequence>();
                        int tmpStartIndex = 0, tmpEndIndex = 0;

                        for (int j = 1; j < result.Length; j++)
                        {
                                if (result[j] == 0 && result[j-1] != 0) tmpStartIndex = j;
                                if (result[j] != 0 && result[j-1] == 0) tmpEndIndex = j - 1;
                                else if (result[j] == 0 && j == result.Length - 1) tmpEndIndex = j;
                                else tmpEndIndex = 0;

                                if (tmpEndIndex != 0) sequences.Add(new Sequence() { StartIndex = tmpStartIndex, EndIndex = tmpEndIndex });
                        }

                        foreach (var sequence in sequences) sequence.SumOfWeightsAround = result[sequence.StartIndex - 1] + (sequence.EndIndex == result.Length - 1 ? result[0] : result[sequence.EndIndex + 1]);

                        // for more longest sequences take the one with minimum surrounding blades weights
                        result[sequences.OrderByDescending(s => s.EndIndex - s.StartIndex).ThenBy(s => s.SumOfWeightsAround).Select(s => (s.StartIndex + s.EndIndex) / 2).First()] = blades[i];
                }

                // the computation is not needed for the last blade
                result[result.Select((v, i) => new { Index = i, Value = v }).Where(e => e.Value == 0).Select(e => e.Index).First()] = blades[blades.Length - 1];

                return result;
        }
}

public class Sequence
{
        public int StartIndex { get; set; }
        public int EndIndex { get; set; }
        public int SumOfWeightsAround { get; set; }
}
 
Nahoru Odpovědět
21. srpna 17:50
Avatar
mifro
Člen
Avatar
Odpovídá na Mouser
mifro:22. srpna 7:13

Ahoj Mouser, to je myslím přesně to, co jsem potřeboval - jdu to přehodit do VB a testovat. Každopádně zatím díky všem!

 
Nahoru Odpovědět
22. srpna 7:13
Avatar
Ghst
Člen
Avatar
Ghst:22. srpna 14:44

Ahoj,
napadá mě jednoduché řešení, ale je to hrubou silou. Zase by si to mělo poradit s různým počtem lopatek a případnými extrémy ve hmotnosti.

  • 1. Vytvořit všechny kombinace lopatek
  • 2. Výpočet těžiště pro daný útvar (namísto délky použít hmotnost lopatky)-
  • 3 . Nalézt těžiště nejblíže středu
Editováno 22. srpna 14:45
 
Nahoru Odpovědět
22. srpna 14:44
Avatar
mifro
Člen
Avatar
Odpovídá na Ghst
mifro:28. srpna 11:14

Ahoj Ghst, vůbec netuším, jak toto provést v kódu...

 
Nahoru Odpovědět
28. srpna 11:14
Avatar
mifro
Člen
Avatar
mifro:1. září 18:49

Tak jsem udělal pokrok. Už si umím spočítat vektory a ukáže mi to kolik gramů dát na jaký úhel pro ideální vyvážení kola. Teď ještě najít ideální rozmístění. Potřeboval bych udělat kombinaci všech hmotností a u každé kombinace spočítat vektory - pak zjistím, která varianta bude mít nejmenší hmotnost.
Poradil byste mi někdo, jak udělat všechny varianty hmotností lopatek? Předpokládám permutace bez opakování. Díky moc.

 
Nahoru Odpovědět
1. září 18:49
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:7. září 0:28

Ahoj mifro,
když to pochopim, tak je určitá šance, že ti s tim pomůžu.
Mám několik dotazů:

  • Je to jen nějaký teoretický cvičení, nebo to má i praktický využití? Je to nějaký statický vyvažování něčeho?
  • Musí být paprsky rozmístěny rovnoměrně? Myslím, musí být všechny úhly stejný?
  • Prošel jsem ve škole nějakou matematikou a myslím si, že chápu, co je to vektor. Jsem si docela jistý, že hmotnost je skalár. Jak to s těma vektorama tedy myslíš? Vektor čeho? Něco společnýho s pozicí těžiště od středu rotace?
  • Jak myslíš "která varianta bude mít nejmenší hmotnost"? Když použiješ všechny paprsky, tak hmotnost budeš mít přeci vždycky stejnou.
 
Nahoru Odpovědět
7. září 0:28
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:9. září 17:25

Ahoj Bugmaster,

  1. jedná se o vyvážení kola axiálního ventilátoru
  2. lopatky mají různé hmotnosti a jde o to je rozmístit co nejlépe kvůli zbytkové nevývaze

Jde o to, najít po zadání hmotností lopatek co nejlepší rozmístění - tzn. navařit na náboj minimální možné závaží.

 
Nahoru Odpovědět
9. září 17:25
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:9. září 21:22

Aha, už mi to začíná dávat smysl. Už chápu, jak jsi myslel tu nejmenší hmotnost.

Takže, oprav mě, pokud se v některém z předpokladů pletu:

  • Lopatky musí být rozmístěny rovnoměrně. Poštelovat úhly tak, aby to vycházelo, není možné, protože takové oběžné kolo by vypadalo divně.
  • Lopatky mají víceméně stejný tvar a tedy i těžiště ve víceméně stejném místě, resp. na stejném poloměru.
  • Když budeš mít různé permutace, podle čeho posoudíš, která je nejlepší? Čím menší vzdálenost těžiště od středu rotace, tím lépe?

Pokud ti jde jen vygenerování všech permutací, tak tam nemusíš nic vymýšlet. Stačí zkopírovat něco, co udělal někdo jiný.

Problém je ale v tom, že počet permutací hodně rychle stoupá s počtem lopatek. Projít je všechny může trvat docela dlouho. Možná to bude chtít něco chytřejšího, než brute force.

Přijde mi to jako úloha na optimalizaci. Teoreticky by k tomu mohl jít přiohnout řešitel v Excelu.

 
Nahoru Odpovědět
9. září 21:22
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:10. září 11:30

Ahoj,

  • V náboji jsou otvory, do kterých se jednotlivé lopatk šroubují - nejde úplně o úhel ale o pořadí.
  • Lopatky jsou tvarově stejné, mohou se lišit hmotností - dáno technologií výroby
  • Permutace - u každé varianty bych spočítal nevývahu a u které by hmotnost vývažku vyšla nejmenší, ta by byla ideální.

Jak píšeš, problém je s počtem variant - např. pro 21 lopatek je to hodně velké číslo.
V příloze je zatím to, co jsem udělal a příklad jak vypadá oběžné kolo. Zadám hmotnosti jednotlivých lopatek, které se mi pak setřídí (použitý návrh Mousera) a spočítá se na jaký úhel navařit kolik gramů. Nicméně i toto řazení není optimální - ručně se dokážu dostat na nižší hmotnost vývažku - viz přiložené screenshoty.

 
Nahoru Odpovědět
10. září 11:30
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:10. září 12:50

Podle mne to potrebujes seradit podle velikosti.
Pak suda-suda a licha-licha by mely byt pary, ktere hledas.

Nebo to seradit nejak tak, aby rozdil hmotmosti paru by mel byt co nejmensi.
abs(a-b) + abs(c-d) + ... = minimum
Coz si myslim, ze by melo resit nebo aspon pomoci prave serazeni podle hmotnosti.

Kde je pak teziste pro dolozeni protizavazi se ale urcuje jinak. To zalezi pak na delce lopatky a jeji vaze a i tak to nebude moc presne...
A ledaco se zmeni po roztoceni, az se soucastky usadi. resp, muze byt teziste jinde pri malych otackach a pri vetsich.
A pak je tu tez vliv prachu a necistot.
Nemas to snadne :)

 
Nahoru Odpovědět
10. září 12:50
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:10. září 13:05
        serazeno;       rozdil od min;  kazda druha, sude radky k sobe, liche k sobe
9       470     0       0
4       475     5       10
2       480     10      22
3       490     20      35
5       492     22      50
1       500     30      5
7       505     35      20
6       510     40      30
8       520     50      40
min     470
 
Nahoru Odpovědět
10. září 13:05
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:10. září 13:11

Vychazi mi to takhle, co se rozdeleni hmotnosti tyce, modry graf.

 
Nahoru Odpovědět
10. září 13:11
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:10. září 13:33

A nebo mozna lepsi, kdyz kazdy druhy par vzajemne vymenis

0       0       470
10      30      500
22      22      492
35      20      490
50      50      520
5       5       475
20      35      505
30      10      480
40      40      510

0-40 zustava
10-30 das opacne jako 30-10

A jeste dalsi tip, to tu bylo zmineno, rozmistovat to do krize a ne poporade.
Vodorovne, svisle, 45 stupnu, -45 stupnu a opet pary, co jsem 0-40, 30-10, 22-35...

Mimochodem, proc je tech cisel 9 a ne 8? To je jako nejak lepcejsi pro vyvazeni?

 
Nahoru Odpovědět
10. září 13:33
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:10. září 14:10

No, a takhle to vypada, jak jsem to myslel uz na zacatku. idealni je co nejvetsi uhly, kruhovy graf (obe moznosti, po sobe i na preskacku). To by melo nejvice snizit vibrace, ikdyz bude treba pridat vetsi zavazi.

50      520     40      510
35      505     35      505
22      492     20      490
10      480     10      480
0       470     0       470
5       475     5       475
20      490     22      492
30      500     30      500
40      510     50      520
 
Nahoru Odpovědět
10. září 14:10
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:10. září 14:20

A jeste 1 obrazek.

 
Nahoru Odpovědět
10. září 14:20
Avatar
mifro
Člen
Avatar
Odpovídá na Peter Mlich
mifro:10. září 14:31

Díky, ale nějak jsem to teď nepobral... nemohl bys mi to prosím ukázat jednoduše v kódu? Já dělám ve ventilátorech a nejsem programátor - to je spíš koníček - občas se snažím udělat něco pro zjednodušení práce. Počet čísel / lopatek resp. hmotností je vždy různý. Většinou něco mezi 6-30 (sudé i liché počty). Jinak jsem zkoušel zadat do mého programu - tvé seřazení ukázalo dovařit závaží 21 gramů, moje řazení 18 gramů. Mám tady jeden příklad z praxe - excel v příloze. Takto jsou hodnoty seřazeny ideálně - ukazuje to 0 gramů. Ale nevidím v tom použitelnou logiku.

 
Nahoru Odpovědět
10. září 14:31
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:11. září 7:58

Ano, urcite to jde vynulovat. Ale kdyz o neco zavadi, tak se ti roztrepe, pokud nevytvoris kruhovy diagram.
Viz tem prvni graf v poslednim obrazku, esicko, tam je v podstate stred na stredu a vpravo a vlevo je zhruba stejny tvar. Ale, kdyz ta vrtulka o neco zavadi, tak vpravo, vlevo bude udrzovat odstredivou silu a nahore se bude kymacet do stran.
A ty tve data jsi dal jako obrazek, to si nemuzu do excelu zkopirovat (musel bych to cislo po cislu opisovat). Jen to oznac, ctrl+c. Klikni sem, klikni tlacitko </> (code) a mezi znacky ctrl+v.

To nedelam programem
min-y2
min+x1
min
min-x2
min+y1
je system, ktery pouzivam. 2 je vyssi hodnota z tech 2 serazenych.

Editováno 11. září 8:00
 
Nahoru Odpovědět
11. září 7:58
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:11. září 8:39
1       10300   10020   0       80      360     280     560                             10020   280
2       10300   10030   10      100     380     280     560                             10300   560
3       10210   10060   40      70      350     110     390                             10060   320
4       10160   10060   40      110     390     110     390                             10210   470
5       10130   10070   50      60      340     80      360                             10090   350
6       10130   10080   60      140     420     80      360                             10130   390
7       10120   10090   70      40      320     60      340                             10030   290
8       10120   10090   70      280     560     50      330                             10100   360
9       10100   10100   80      10      290     10      290                             10120   380
10      10100   10100   80      0       280     0       280                             10070   330
11      10090   10120   100     280     560     40      320                             10300   560
12      10090   10120   100     40      320     40      320                             10060   320
13      10080   10130   110     190     470     70      350                             10160   420
14      10070   10130   110     50      330     70      350                             10090   350
15      10060   10160   140     110     390     100     380                             10130   390
16      10060   10210   190     70      350     100     380                             10080   340
17      10030   10300   280     100     380     140     420                             10100   360
18      10020   10300   280     80      360     190     470                             10120   380

Mozna, po chvili premysleni nebo googlovani bych nasel reseni i na kruhove rozmisteni se stredem uprostred. Tento problem je uz urcite davno vyreseny. PS. Pouzil jsem OCR, ale stejne jsem musel nejake cisla opravovat.

 
Nahoru Odpovědět
11. září 8:39
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:11. září 8:43

Ten oranzovy graf mozna vypada jako zahada, ale postup je podobny jako u predchoziho. Jdu po serazenych cislech, jednou cislo dam nahoru, podruhe dolu. Na prskascku, takto mensi nahoru - vetsi dolu, mensi dolu - vetsi nahoru... Muzu ti to zas barevne oznacit.

 
Nahoru Odpovědět
11. září 8:43
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:11. září 9:35

Jo, a tohle je podle schematu ze vcera.
Rozdelis to napul a cisla rozdeluje na radek 1, (n/2), 2, (n/2)+1, ...
A druhe je totez, jen beres jedno cislo zhora, druhe ze spode a delas pary zhora+zespodu, zespodu+zhora. Nechce se mi delat ted screen. V druhem pripade jsem dostal hodne podobny tvar tve hvezdici.

10      290     280     560
40      320     10      290
60      340     190     470
70      350     40      320
80      360     110     390
100     380     60      340
110     390     100     380
140     420     70      350
280     560     80      360
0       280     0       280
40      320     280     560
50      330     40      320
70      350     140     420
80      360     50      330
100     380     110     390
110     390     70      350
190     470     100     380
280     560     80      360
Editováno 11. září 9:36
 
Nahoru Odpovědět
11. září 9:35
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:11. září 20:12

Vzal jsem hmotnosti z úplně prvního příspěvku a zkusil jsem to prohnat řešitelem v Excelu. Jestli jsem to správně pochopil a realizoval, tak by to mělo být o chloupek lepší, než tebou navržené řešení. Moje reseni je v tom modrym zaramovani.

 
Nahoru Odpovědět
11. září 20:12
Avatar
mifro
Člen
Avatar
Odpovídá na Peter Mlich
mifro:12. září 17:53

Díky, ten zelený graf vypadá perfektně - zkusím se v tom zorientovat. Jinak pro info, lopatka nikde zavadit nemůže - resp. 2-tunové kolo o průměru 3 metry se 775 otáčkami zavadí jen jednou ;-)

 
Nahoru Odpovědět
12. září 17:53
Avatar
mifro
Člen
Avatar
Odpovídá na Peter Mlich
mifro:13. září 7:33

Peter Mlich - já se omlouvám, ale koukal jsem na to a úpně tomu nerozumím - jakým systémem seřadím hodnoty, abych dostal zelený graf? Nemohl bys mi prosím dát názorný příklad? Díky moc.

 
Nahoru Odpovědět
13. září 7:33
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:13. září 7:50

Zeleny graf jsou tve hodnoty. Obrazek jsem tam dal pro srovnani. Je na nem videt urcita symetrie rozlozeni kolem kruhu uprostred.
Posilam obrazek z hodnot, ktere jsem tam pridal pak.

 
Nahoru Odpovědět
13. září 7:50
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:13. září 8:02

V te druhe casti jsem zkousel dalsi logickou variantu. Rozdelit kolo na 4 casti a stridat velke-male cislo jako par lopatek proti sobe.
(male 1) 2 3 4 (velke 5) 6 7 89

  9      2
    \  |
1 ------------ 5
       |   \
       6    4

1 - 5, pak do krize 2 - 6 a pro vyvazeni mezi 1-2 vlozit velke cislo od konce 9 a k nemu par 4 do protivky. Atd.

A samozrejme to ted rikam blbe, bylo by mozna lepsi i tu serazenou radu rozdelit po ctvrtitach a tak pridelovat cisla. Rozdil cisel v paru by mel byt co nejmensi.
Ale, pokud nechces neco takoveho jako ten obrazek S nebo zubate kolo, dvojite S do krize, ale chces hvezdu, tak je lepsi to parovat prave male-velke cislo a rozdil je 1/4.

 
Nahoru Odpovědět
13. září 8:02
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:13. září 8:29

Nebo, mozna si to pletu, mozna ses ptal na zeleny graf v prispevku
"A jeste 1 obrazek."
https://www.itnetwork.cz/…0662_image_0

Tam zeleny graf, no, jak to popsat.
Serazena cisla rozdelis na dve pulky.
Pro ukladani cisel rozdelis na 2 pulky (parovani)
0 cislo zhora, 30 cislo zhora pulka2
5 cislo zhora, 35 cislo zhora pulka2, 10 cislo zhora, 40 cislo zhora pulka2
20 cislo zhora, 50 cislo zhora pulka2, ...
Je to zas jeden pokus, jak vyvazit kolo, rozdelit cisla rovnomerne a na stridacku. Ten obrazec by vypadal lepe, kdybych pouzil system z druheho sesitu pro ten vetsi pocet hodnot.
Pozn:

  • zhora je mysleno jakoze zhora, nepridelene cislo.
  • poloha 0, 5 je dana, musi byt doprotivky na kole, proto je 0 na prvnim radku a 5 na radku 4 nebo 5, to je na tobe
  • system je voleny tak, aby rozdil protilehlych cisel byl 50%. Proto se bere jedno cislo zhora a druhe az od poloviny serazene rady.
 
Nahoru Odpovědět
13. září 8:29
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:19. září 14:01

Ten řešitel resp. jeho výpočet jde nějak "převést" do kódu?

 
Nahoru Odpovědět
19. září 14:01
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:19. září 14:36

Algoritmy, které Excel k tomuhle ve střevech používá, jsou obecně známé. Tak snad se našel někdo, kdo to přepsal do dotnetu (přeci jen je to jedna z nejrozšířenějších platforem).

Zatím jsem se zběžně díval na OR-Tools od Googlu, ale zdá se, že ten k tomu použít nepůjde (patrně se nejedná o lineární optimalizaci). Určitě ale někde někdo napsal něco použitelnýho a chce to "jen" najít. Až budu mít pár hodin v kuse čas, tak se na to podívám. Tohle je docela zajímavý porblém.

 
Nahoru Odpovědět
19. září 14:36
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na mifro
Peter Mlich:20. září 10:06

Mimochodem, nemuzes poslat soubor, ten xls? Ja bych tam testnul ty moje varianty, jak to vychazi. Nechce se mi ted vymyslet algoritmus, ktery proveri vsechny moznosti nebo nejakou matematicko-fyzikalni rovnici. Spis tak, proo zajimavost.

 
Nahoru Odpovědět
20. září 10:06
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:20. září 10:41

Včera při čištění zůbů mě napadl jednoduchý algoritmu, který nazahrnouje žádnou složitou optimlalizace.

V podstatě to funguje takhle:

  1. Vezme vstupní hodnoty a "vyrobí" z nich oběžné kolo. Následně zkouší prohodit vždycky pár lopatek a zkouší, která verze je nejlepší (= má těžiště nejblíže středu).
  2. Vezme nejlepší verzi a opakuje od bodu 1 dokud došlo k nějakýmu prohození (v určitým momentu každé prohození vede ke zhoršení).

Výhoda je, že při každé iteraci je třeba projít pouze n*(n-1)/2 variant oběžného kola (n je počet lopatek), což není tak mnoho.

Naimplementoval jsem to ve vb.net, takže by neměl být problém, kdybys to nejdebože chtěl použít.

Vypisuje to tohle. (hehe, mám zdroják s idečkem 1234, heč!)

 
Nahoru Odpovědět
20. září 10:41
Avatar
Bugmaster
Člen
Avatar
Odpovídá na Peter Mlich
Bugmaster:21. září 9:04

Teď si nejsem jist, který excel myslíš (reaguješ na mifra). Pokud ten můj výplod s tím řešitelem, tak tady ho máš.

Jenom si nejsem úplně jist, jestli ti to k něčemu bude :/

 
Nahoru Odpovědět
21. září 9:04
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:21. září 15:17

Bugmaster: Díky a gratulace k idečku :-D Jinak to vypadá perfektně - budu zkoumat a testovat.

 
Nahoru Odpovědět
21. září 15:17
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:22. září 20:59

Jeste jsem s tim nebyl spokojenej. Tenhle algoritmus zavisi na vstupnich hodnotach a nezajisti vzdy nejlepsi mozny vysledek. Tak jsem vymyslel, ze lopatky zkusim nekolikrat (deterministicky) promichat a optimalizuju jednotlive verze. Az z tech pak vyberu tu nejlepsi. Funguje to docela dobre.

Uz to ale nebylo rozumny cpat do jednoho souboru, tak jsem zpublikoval repozitar, kde si to muzes stahnout.

Pro vetsi kola to muze trvat docela dlouho. Je tam ale prostor pro zrycheni - tohle by melo jit snadno rozlozit do vice vlaken. A mozna tam man nekde nejakou botu, ktera to brzdi :/ To se obcas taky stava (viz můj nickname).

 
Nahoru Odpovědět
22. září 20:59
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:23. září 8:14

K promichani se da pouzit serazovaci algoritmus s podminkou, ze 0.66 a vic, aby to co nejvic promichal. Ale nevim, jak se to ve VB pise. V JS by to vypadalo nejak takto

<script>
function sortCmp(a, b) {return 0.66-Math.random();}
arr = [1, 2, 3, 4];
arr.sort(sortCmp);
alert(arr);
</script>

U normalniho sortu porovnava vzdy 2 hodnoty, a, b. Vysledek operace je bud a\<b nebo a\>\=b nebo -1 +0 +1. A podle toho se bud a vymeni za b nebo ne. Cili, kdyz se tam da prvek random a vysledek nastavi cie plusovy, proto 0.66 a ne 0.5, tak bude a,b vic vzajemne vymenovat. Ale nesmis tam dat 0 protoze nic neseradi a nesmis dat 1 protoze budou jen v opacnem poradi.

A nebo zrovna pouzij serazovani jako zpusob prochazeni pole pro hledani vysledku, kde tu funkci prepises na tvoji.

<script>
function sortCmp(a, b) {return jeVicVyvazenejsi(a,b);}
arr = [1, 2, 3, 4];
arr.sort(sortCmp);
alert(arr);
</script>

Proc? Nativni funkce byvaji obvykle optimalizovane, rychlejsi.

Editováno 23. září 8:15
 
Nahoru Odpovědět
23. září 8:14
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:23. září 8:18

Ted porovnavas pary a, b a skocis na dalsi par. Slo by treba v druhe fazi zkusi jako par pouzit a+1, b. Lopatky, ktere nejsou uplne proti sobe je zkusit vymenit.

 
Nahoru Odpovědět
23. září 8:18
Avatar
Bugmaster
Člen
Avatar
Odpovídá na Peter Mlich
Bugmaster:23. září 10:37

Mě ale nešlo o to seřadit je náhodně. Já je chtěl seřadit deterministicky - tak, aby byly rozházený, ale požadý rozházený stejně. Když je rozházim náhodně, tak hrozí, že při každym volání funkce dostanu na stejný vstup jiný výstup. To se mi nelíbí, proto jsem si dal tu práci s vymýšlením algoritmu, který to míchá deterministicky.

K tomu jak píšeš:

function sortCmp(a, b) {return 0.66-Math.random();}

Když použiješ komparační funkci timhle způsobem, nebojíš se trochu? Takhle ta funkce není tranzitivní (neplatí: jestliže a < b AND b < c potom a < c). Představ si, že tohle použiješ na rozházení dlouhý posloupnosti třeba nějakým bubble sortem: ukončí se to jen v případě, že ti ve všech porovnáních zrovna padne výsledek "menší než 0", což záleží na náhodě.

Jak píšeš "Nativni funkce byvaji obvykle optimalizovane, rychlejsi.".
Ano, to máš pravdu. Jenže já nepotřebuju seřadit možná řešení od nejlepších po nejhorší. Já potřebuju najít to jedno řešení, které je nejlepší. A k tomu stejně musím projít všechny návrhy.

Ted porovnavas pary a, b a skocis na dalsi par. Slo by treba v druhe fazi zkusi jako par pouzit a+1, b. Lopatky, ktere nejsou uplne proti sobe je zkusit vymenit.

V každé iteraci vyzkouším prohodit úplně všechny páry. Jednotlivá prohození si představ jako hranu úplného grafu (alespoň já si to tak v hlvě vizualizuju).

 
Nahoru Odpovědět
23. září 10:37
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:23. září 12:19

Díky, zkouším to nahodit do mého "výtvoru" a asi už jsem blbej, ale nemůžu přijít, jak převést hodnoty / hmoptnosti z listboxu do Dim zadaniList As New List(Of Double()) From {
New Double() {500.0, 480.0, 490.0, 475.0, 492.0, 510.0, 505.0, 520.0, 470.0}}
Tzn. místo ručně zadaných hodnot tam načíst listbox. Zkoušel jsem for xx=0 to listbox1.item­s.count do zadanilist(xx)=lis­tbox1.items.i­tem(xx) next ale bez úspěchu...

 
Nahoru Odpovědět
23. září 12:19
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:23. září 13:07

Někde si psal, že si použil algoritmus od Mousera, že?

To znamená, že umíš z ListBoxu sestavit pole intů s hodnotama hmotností.

V tom případě by ti pak měla stačit následující funkce, která spapinká stejný vstup a vrátí ti seřazený výstup.

''' <summary>
''' Vrati pole serazenych hodnot.
''' </summary>
''' <param name="hmotnosti">hodnoty k serazeni</param>
Function Seradit(hmotnosti As IEnumerable(Of Integer)) As Integer()
  ' Inicializovat optimalizer, ktery provadi samotny algoritmus
  Dim rozvazny = New RozvaznyOptimalizer("Rozvazny")

  ' Zabalit ho do wrapperu, ktery bude zkouset ruzne promichany vstupy
  Dim kolikratPromichat = 30
  Dim rozvaznyScrambled = New ScrambleOptimalizer("Zamichany rozvazny", kolikratPromichat, rozvazny)

  ' Vytvorit kolo (ve vnitr pracuju s Doublama, vstup jsoi inty takze to potrebuju konvertovat)
  Dim pocatecniKolo = New Kolo((From h In hmotnosti Select CDbl(h)).ToArray())

  ' Optimalizovat
  Dim optimalizovaneKolo = rozvaznyScrambled.Optimalizovat(pocatecniKolo)

  ' Vratit vysledne poradi (tady to zase konvertuju zpet z doublu do intu)
  Return (From h In optimalizovaneKolo.SerazeneHmotnosti Select CInt(h)).ToArray()
End Function

Vola se to pak nejak takto:

' Musis nejak sestavit pole nebo list integeru, ktere nejakym zpusobem prectese z ListBoxu
Dim hodnotyZListBoxu = New Integer() {500, 480, 490, 475, 492, 510, 505, 520, 470}

' Zoptimalizovat. Vysledek je zase pole integeru.
Dim zoptimalizovano = Seradit(hodnotyZListBoxu)

' Pak to dale zpracovat. Treba vypsat nebo cokoliv
Console.WriteLine(String.Join(", ", zoptimalizovano))
 
Nahoru Odpovědět
23. září 13:07
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:23. září 13:52

Díky, zkouším to - ještě jedna věc - jak pak dostanu do druheho listboxu vysledky? (jedna lopatka/hmotnost = 1 řádek) V msgboxu mi to vyjede, ale....
MsgBox("finální kolo: " & String.Join("; ", From l In kolo Select String.Format("{0:N1}", l.Hmotnost)))
Díky a omlouvám se, že prudím s kravinama, ale tohle už je pro mě vyšší dívčí :-D

 
Nahoru Odpovědět
23. září 13:52
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:23. září 14:31

Tak jsem trochu zabojoval a zde je výsledek. Nevypadá to úplně špatně, že?

 
Nahoru Odpovědět
23. září 14:31
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:23. září 14:42

Já si řikal, že tě v tom nechám trochu potrápit :) S těmahle pakárnama se blbě radí, protože netuším, jak to máš ve vnitř realizovaný.

Kolik byl ten vývažek předtím?

 
Nahoru Odpovědět
23. září 14:42
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:23. září 14:55

:-D před tím jsem měl 18g. Teď to budu porovnávat se starým ručním řazením, co mám v excelu. Myslím si, že nyní je to optimální. A snad i hmotnost vývažku a úhel kam ho navařit počítám správně ;-)

 
Nahoru Odpovědět
23. září 14:55
Avatar
mifro
Člen
Avatar
Odpovídá na mifro
mifro:23. září 15:34

Např. pro hodnoty níže (reálné hmotnosti již namontovaných lopatek) mi to ukazuje 1273 gramů na 350°. Zkusíš pro zajimavost ověřit? Díky

7273
7140
7187
7204
7147
7243
7169
7195
7182
7218
7125
7253
7195
7133
7203
7168
7236
7179
7234
7129
7202

 
Nahoru Odpovědět
23. září 15:34
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:23. září 16:15

Jak to myslíš ověřit? Nenaimplementoval si právě to řazení do programu?

Když to proženu algoritmem, tak mam tuhle posloupnost:

7253
7204
7133
7182
7129
7234
7243
7236
7125
7187
7168
7169
7273
7195
7147
7179
7218
7203
7140
7195
7202

Excentricita těžiště je nula nula prd. Kolik přidat, to nevím, protože neznám žádný dimenze.

 
Nahoru Odpovědět
23. září 16:15
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:24. září 6:57

Používám v podstatě "jen" tento příkaz (seřazené lopatky do listboxu) :

Dim zoptimalizovano = Seradit(hodno­tyZListBoxu)
For ss = 0 To ListBox1.Item­s.Count - 1
ListBox2.Item­s.Add(zoptima­lizovano(ss))
Next
Výsledky stejné, tak to je OK.

 
Nahoru Odpovědět
24. září 6:57
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:24. září 7:22

Tak takhle nějak jsem tu funkci zamýšlel.

Při tomhle řazení to chce doplnit vyvážení 1273 g?

 
Nahoru Odpovědět
24. září 7:22
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:24. září 7:47

Lopatky mají celkem 150kg, náboj má 900kg - 1,2kg je ok. Ale ještě to zkusím přepočítat ručně na zkoušku.
Jinak hodnota Dim kolikratPromichat = 30 má nějaký velký vliv? Ať dám 1 nebo 500, výsledky jsou stejné a ok.
Díky

 
Nahoru Odpovědět
24. září 7:47
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:24. září 9:21

Je to číslo, které říká, kolik se má vytvořit různě promíchaných verzí oběžného kola, které se následně zkouší optimalizovat a z nich se vybere to nejlepší. Takže určitě to má vliv na dobu trvání optimalizace - a to přímo úměrnou.

Jestli to má vliv na výsledek? Na to mám dvě verze odpovědi:

Zkrácená verze:
Podle mých měření má. Jestli je to významný vliv? To si musíš posoudit sám.

Plná verze:
Algoritmus funguje tak, že v podstatě odzkouší hromadu verzí oběžného kola s různě proházenýma lopatkama. Z těchle verzí následně vybírám to nejlepší. Aby jsem mohl vybrat to nejlepší, tak je potřebuji nějak porovnat. Porovnávám je tím způsobem, že každý verzi oběžného kola připlácnu nějaké číslo, které vyjadřuje jak moc je to dobré řešení. Protože mě nenapadlo nic lepšího, tak to číslo je výstřednost těžiště sestavy lopatek (s tím, že počítám, že těžiště lopatky leží na poloměru jedna, ať už je to jakákliv vzdálenost).

A podle mých měření to na výstřednost těžiště vliv má:

Jestli to má vliv na výsledné hmotnosti vývažku? To si budeš muset rozhodnout sám.

 
Nahoru Odpovědět
24. září 9:21
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:24. září 10:27

Tady je zatím skoro-finální podoba ;-) Myslím, že to počítá perfektně, ale čeká mě ještě hodně testů.

 
Nahoru Odpovědět
24. září 10:27
Avatar
Ghst
Člen
Avatar
Ghst:24. září 10:57

Ahoj,

tak jsem se vrátil po delší době. Dáš mi nějaké data, na kterých mohu otestovat své řešení?

Jak píšeš, problém je s počtem variant - např. pro 21 lopatek je to hodně velké číslo.

Brute force, nebude tak velké číslo, není třeba procházet všechny možné kombinace (ne)vyváženost pro rozložení
1, 2, 3, 4, 5
bude stejná jako, pouze posunuté
2, 3, 4, 5, 1
3, 4, 5, 1, 2
...
5, 1, 2, 3, 4
a otočené
5, 4, 3, 2, 1
...

 
Nahoru Odpovědět
24. září 10:57
Avatar
mifro
Člen
Avatar
Odpovídá na Ghst
mifro:24. září 11:10

Ahoj, zkus můj obrázek nad tvým postem a data jsou zde:
10300
10030
10120
10050
10210
10050
10130
10090
10100
10300
10100
10090
10130
10070
10160
10080
10120
10020

 
Nahoru Odpovědět
24. září 11:10
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:24. září 11:31

Vam to pocita jako 10s? Mne to s tim sortem pocita ms. Ale urcite ne tak dobre jako ty vase reseni.
https://mlich.zam.slu.cz/js-teziste.htm

 
Nahoru Odpovědět
24. září 11:31
Avatar
Ghst
Člen
Avatar
Ghst:24. září 13:01

Vyleza mi tahle posloupnost, můžeš ověřit jak si stojí?

10120
10050
10210
10050
10130
10090
10030
10100
10300
10100
10090
10130
10070
10160
10080
10120
10020
10300

PS: jak počítáš jakou hmotnost a kam máš přidat?

Není lepší přidávat jedno těžší závaží, než 2 lehčí?

 
Nahoru Odpovědět
24. září 13:01
Avatar
mifro
Člen
Avatar
Odpovídá na Ghst
mifro:24. září 13:11

Viz příloha - obr moje / tvoje. Na mém je vidět 1 gram, na tvém 28 gramů. Závaží je jen jedno - vidíš tam úhel, kam ho připevnit.

 
Nahoru Odpovědět
24. září 13:11
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:24. září 15:12

Upravil jsem ten muj program na nahodne serazeni a pak 3x zkusit optimalizovat a cele to jeste 1000x zopakovat. Dava to celek slusne vysledky se vzdalenosti 0. Neprisel jsem na to, jak pocitas hmotnost. To v tom XSL, co jsi kdysi posilal, neni.
https://mlich.zam.slu.cz/js-teziste.htm
Mne vychazi pri nekolika F5 treba tohle. Snad tam neni chyba...

({x:5.7e-7, y:-7.4e-7, m:182170, vz:9.3e-7}
10130
10100
10300
10090
10060
10060
10300
10020
10080
10090
10120
10130
10160
10210
10120
10070
10100
10030
 
Nahoru Odpovědět
24. září 15:12
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Peter Mlich
Peter Mlich:24. září 15:15

Jo, zdrojovy kod se da zobrazit primo v prohlizeci. Je to zplacane narychlo, tak moc na to nekoukat :)

 
Nahoru Odpovědět
24. září 15:15
Avatar
Bugmaster
Člen
Avatar
Odpovídá na mifro
Bugmaster:24. září 15:22

Ten graf se mi líbí. Ještě do toho vyznačit kam přijde vyvážka a je to dokonalý.

Takže počet míchání je Accuracy? :)

 
Nahoru Odpovědět
24. září 15:22
Avatar
Bugmaster
Člen
Avatar
Odpovídá na Ghst
Bugmaster:24. září 15:22

Sakra, to mě nenapadlo! To máš pravdu! To by potenciálně šlo, ale nenapadá mě, jak alespoň napůl rozumně vygenerovat všechny varianty :(

 
Nahoru Odpovědět
24. září 15:22
Avatar
Bugmaster
Člen
Avatar
Odpovídá na Peter Mlich
Bugmaster:24. září 15:23

Jóó tohle... to záleží. V krajních případech ano :( Prochází to hodně variant. Kdyby to byl problém, tak se to dá potenciálně zrcyhlit - jednak paralelním výpočtem jednolivých variant a potenciálně možná taky některé varianty přeskočit - viz to co psal Ghst.

 
Nahoru Odpovědět
24. září 15:23
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:24. září 15:33

ano, accuracy. pozici závaží už jsem dodělal - po zadání průměru náboje to ukáže kolik mm se vývažek umístí za kolikátou lopatkou.

 
Nahoru Odpovědět
24. září 15:33
Avatar
Bugmaster
Člen
Avatar
Odpovídá na Peter Mlich
Bugmaster:24. září 21:02

Nevím, jak se ti to podařilo, ale řadí ti to fakt dobře a rychle (a nevyzpytatelně). V tom kódu se ale vůbec nevyznám :/ Takhle na první pohled mi přijde, že se to trochu zhoršuje se stoupajícím počtem lopatek, ale stále je to imho naprosto ok.

Kdyby to vysvtělil nebo přepsal jako pro blbý (tj. jako pro mě), tak to můžu přepsat do VB a navrhnout to mifrovi.

Neprisel jsem na to, jak pocitas hmotnost. To v tom XSL, co jsi kdysi posilal, neni.

Jsem přesvědčenej, že hmotnost vývažku ze zadaných údajů spočítat nemůžeš. Neumím si představit, že bych to počítal bez znalosti na jakým poloměru je těžiště lopatky a na jaký poloměr se navařuje závaží. Nebo mi něco uniká?

 
Nahoru Odpovědět
24. září 21:02
Avatar
Mouser
Člen
Avatar
Odpovídá na Bugmaster
Mouser:24. září 23:30

Jsem přesvědčenej, že hmotnost vývažku ze zadaných údajů spočítat nemůžeš. Neumím si představit, že bych to počítal bez znalosti na jakým poloměru je těžiště lopatky a na jaký poloměr se navařuje závaží. Nebo mi něco uniká?

Podle mě můžeme rozdíly v poloměru u jednotlivých lopatek zanedbat, protože budou mít řádově menší vliv na výsledek než rozdíly v hmotnostech. Jde určitě o to, aby se vyrovnaly účinky odstředivé síly jednotlivých lopatek. Odstředivá síla lopatky je m * ω^2 * r, kde rychlost otáčení je pro všechny lopatky stejná, a rozdíly v hmotnostech jsou v řádu jednotek. To by musely být rozdíly v poloměru v řádu metrů, což jistě nebudou. :-) Takže vývažek můžu spočítat jednoduše tak, že ve směru jednotlivých lopatek vynesu vektory, kde každý bude mít velikost úměrnou hmotnosti lopatky, spočítám jejich výslednici, a vývažek bude mít stejnou velikost jako výslednice (velikost odpovídá hmotnosti), akorát bude směřovat na opačnou stranu. Tedy nejsem strojař, ale přijde mi, že to takhle musí být.

To, co psal Ghst, mě napadlo taky, ale ono to zas tolik nepomůže. Pokud se nepletu, tak to posouvání začátku mi vydělí výsledek n-krát (mám n lopatek, na kterých může posloupnost začít) a zrcadlení ještě dvakrát. Čili výsledná náročnost výpočtu je 1/2 * (n-1)! To je sice hezké, ale při základu okolo 20 už je to oproti n! asi jedno. Ostatně můžeme si představit, že jednu lopatku umístíme fixně (je jedno, na který úhel), a hledáme rozložení jen těch zbylých, a tam už začátek sekvence posouvat nemůžeme, čili je jasné, že výsledek musí být úměrný faktoriálu n-1 (zbyde tam jen to dělení dvojkou díky zrcadlení).

Chtělo by to kontaktovat někoho, kdo se vyzná v kapitole matematiky, které se říká operační výzkum, protože to určitě bude úloha na něco z toho. Popis řešení (počáteční rozložení si nějak zvolím, pak prohazuju lopatky dokud se výsledek zlepšuje, ale musím začít několikrát, protože nevím, jestli má funkce jen jedno lokální minimum) celkem přesně odpovídá popisu řešení u nelineárního programování. V tom už se nevyznám, ale klasické lineární programování, které jsem se kdysi učil, funguje pro spojité spektrum přípustných výsledků, a nevím, jak by se zapsaly omezující podmínky, že hmotnost lopatek není spojitá, ale vybírám ji jen z dané množiny.

Jinak teď už je to asi jedno, ale ještě mě napadl algoritmus, který by pracoval zhruba tak, že si kolo rozdělím na X segmentů, a snažím se do segmentů rozmisťovat lopatky tak, aby měly segmenty co nejvyrovnanější hmotnost. Když si představím kolo, které má na jedné půlce všechny těžké lopatky a na druhé všechny lehké, tak takové kolo určitě optimální nebude, a nezáleží, jak budou ty těžké ani lehké lopatky proházené, čili všechny tyhle permutace můžu rovnou zahodit. Resp. naopak můžu rovnou rozdělit lopatky na dvě poloviny tak, aby měly ty poloviny co nejvyrovnanější hmotnost. Pak udělám totéž pro třetiny, pak pro čtvrtiny atd. A mělo by mi postupně vyjít, kam kterou lopatku umístit. Ale nevím, jak dobře by to fungovalo, je to jen námět.

 
Nahoru Odpovědět
24. září 23:30
Avatar
Bugmaster
Člen
Avatar
Odpovídá na Mouser
Bugmaster:25. září 6:38

Wow, narazil jsem na notifikační e-mail hned po probuzení a musím konstatovat, že mě tvůj příspěvek úspešně probral :)

Podle mě můžeme rozdíly v poloměru u jednotlivých lopatek zanedbat...

Tak jsem to nemyslel. Myslel jsem to tak, že hmotnost, kterou je třeba přidat (nebo odebrat na druhé straně) nespočítám pouze ze znalosti hmotnosti a rozmístění jednolivých lopatek. Já bych na to totiž šel takto:
Z poloměru, na kterém leží těšitě lopatek bych spočítal skutečno polohu těžiště soustavy lopatek. Z toho znám úhel a poloměr, na kterém těžiště leží. Závaží pak umístit na druhou stranu a vyvážit to jako houpačku - a k tomu potřebuju znát poloměr, kam přijde závaží (nebo hmotnost a určit poloměr, to ale asi není moc praktické).

 
Nahoru Odpovědět
25. září 6:38
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Bugmaster
Peter Mlich:25. září 7:59

Presne, jak pises. Teziste celeho telesa lze spocitat jen z celeho telesa. Ty lopatky, to take neni kolesovy parnik, ale jsou ruzne zkroucene a v nejake vzdalenosti od stredu. Ten priklad je tedy znacne zjednoduseny jen na hmotnosti lopatek, podle mne.

Ten kod do VB psat nebudu. Dneska mne mozna napadla jeste lepsi varianta. Zkusim popsat.

  • nahodne zamicham
  • vyuziji iteraci sortovaciho algoritmu (jinak bych pouzil cyklus s nahodnym vyberem)
  • vemu tak nahodne 2 lopatky, spocitam T1, prohodim je, spocitam T2. Porovnam T1 a T2. Pokud je vzdalenost mensi, tak je vymenim.
  • spustim to 2x, protoze jsem si vsiml, ze to jeste trosku ubere. (mam to 3x, pro jistotu, ale nevsiml jsem si zmeny)
  • a cely program spusitm 1000x

Co by se dalo vylepsit?

  • sortovaci algoritmus na zamichani necham
  • ale pro nahodny vyber lopatek zkusim ten cyklus
  • nepocitat T1, ale ulozit z predchoziho
  • nepocitat cele T1, ale odecist a pricist vymenovane lopatky
  • nepocitat celkovou hmotnost pro T, ta je pro vsechny stejna
PERF.getTime();
for (i=0; i<1000; i++)
        {
        lop.sort(func.sort2Cmp);        // serad random
        lop.sort(func.sort1Cmp);        // optimalizuj
        app.vars.lop = lop;
        lop.sort(func.sort1Cmp);        // optimalizuj
        app.vars.lop = lop;
        lop.sort(func.sort1Cmp);        // optimalizuj
        app.vars.lop = lop;
        func.saveBest(lop);
        }
time = PERF.getTime();

S tim sortem to funguje tak, ze algoritmus ma konecny pocet iteraci a pri prvni prochazi vsechny hodnoty. Pak uz jen ty, ktere nejsou serazene (kdyby slo o cisla). Proste to pouzivam misto while/for cyklu, ktery tam pouzivas ty. Takova finticka. Proti tvemu by to mohlo davat mozna i horsi vysledky, ale :)

 
Nahoru Odpovědět
25. září 7:59
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Peter Mlich
Peter Mlich:25. září 8:02

Jinymi slovy, pocitam, ze teziste, cela hmotnost lopatky, je uprostred ve vzdalenosti 0 od stredu. Zadna vaha soukoli, naboju ani vychyleni nebo vzdalenejsi blizsi zasunuti lopatky ke stredu.
Odhadem bych dovazku poctal jako prumer hmotnosti * vzdalenost.

 
Nahoru Odpovědět
25. září 8:02
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:25. září 9:36

Ted jsem to cele predelal. A nejsem si ted moc jisty puvodnim vysledkem, kde mi to hazelo pekna cisla, kdezto todle zatim nee a pritom to ma lepcejsi algoritmy. A vystup jeste ladim.
https://mlich.zam.slu.cz/js-teziste.htm
Treba, proc vymenovat vsechno, kdyz muzu vymenit jen vahu.

app.func.telesoTezisteSwap = function(t, swap_a, swap_b)
        {
        t    = app.func.cloneT(t);
        t.x *= t.m;
        t.y *= t.m;
        t.x -= swap_a.x * swap_a.m;     // odectu puvodni
        t.y -= swap_a.y * swap_a.m;
        t.x -= swap_b.x * swap_b.m;
        t.y -= swap_b.y * swap_b.m;
        t.x += swap_a.x * swap_b.m;     // prictu s vymenou hmotnosti
        t.y += swap_a.y * swap_b.m;
        t.x += swap_b.x * swap_a.m;
        t.y += swap_b.y * swap_a.m;
        t.x /= t.m;
        t.y /= t.m;
        t.vz = Math.sqrt(t.x*t.x + t.y*t.y);
        return t;
        }
Editováno 25. září 9:37
 
Nahoru Odpovědět
25. září 9:36
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:26. září 8:47

Podarilo se mi to vic optimalizovat.
Pro jistotu je dobre spocitat teziste uplnou funkci, krome te zkracene. Vcera jsem stravil asi 4h hledanim chyby jen proto, ze jsem po zamichani nespocital znovu teziste :) Pak mi vychazela fantasticka cisla. Zkuste to nekdo proverit, ze zadate nejaka data, u kterych vite vysledek. To by melo byt to prvni teziste, z puvodnich dat a pod nimi jsou dve nova a zobrazi nova data. Takze, kdyz to bude vychazet 0, tak by to melo zobrazit zadani. Opakovani mam 10.000. U mne to pocita asi 250 ms.

Editováno 26. září 8:48
 
Nahoru Odpovědět
26. září 8:47
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Peter Mlich
Peter Mlich:26. září 8:53

graf to nejspis nezobrazuje dobre, teziste, nereste :)

 
Nahoru Odpovědět
26. září 8:53
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:26. září 13:15

Graf opraveno. A jeste jsem to vylepsil takovou drobnosti....

  • Da se nastavit cas, jak dlouho to ma pocitat (posledni radky kodu). On si sam urci pocet cyklu. Kdyz se tam da moc hodnot, tak to nepocita dlouho.
  • Graf je mozne vypnout. Zkusil jsem dat 100 cisel a nejak dlouho to vykreslovalo. Musel bych to predelat js-html na js-canvas. Ve FF asi 1s
  • Vstup je mozne zadat s carkami. Takze je mozne vykopirovat vysledky od bugmastera.

... vyhoda js je, ze funguje i na linuxu, applu. Takze by to bylo mozna lepsi nez vba.

 
Nahoru Odpovědět
26. září 13:15
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:27. září 7:55

Prepsal jsem to na cykly, treba to bude srozumitelnejsi nez s tim sortem. Tohle je zakladni kod rozhodovani
http://mlich.zam.slu.cz/…te-cycle.htm

app.func.telesoTeziste = function(lop)
        {
        var i, i_max, t;
        t     = {x: 0, y: 0, m: 0, vz: 0};
        i_max = lop.length;
        if (isExist(app.vars.tez))
                {
                for (i=0;i<i_max;i++)
                        {
                        t.x += lop[i].x * lop[i].m;
                        t.y += lop[i].y * lop[i].m;
                        }
                t.m = app.vars.tez.m;
                }
        else
                {
                for (i=0;i<i_max;i++)
                        {
                        t.x += lop[i].x * lop[i].m;
                        t.y += lop[i].y * lop[i].m;
                        t.m += lop[i].m;
                        }
                }
        t.x /= t.m;
        t.y /= t.m;
        t.vz = Math.sqrt(t.x*t.x + t.y*t.y);
        return t;
        }

app.func.telesoTezisteSwap = function(t_old, swap_a, swap_b)
        {
        var t;
        t    = app.func.cloneT(t_old);
//screen.write(t.toSource());
//screen.write(swap_a.toSource());
//screen.write(swap_b.toSource());
        t.x *= t.m;
        t.y *= t.m;
        t.x -= swap_a.x * swap_a.m;     // odectu puvodni
        t.y -= swap_a.y * swap_a.m;
        t.x -= swap_b.x * swap_b.m;
        t.y -= swap_b.y * swap_b.m;
        t.x += swap_a.x * swap_b.m;     // prictu s vymenou hmotnosti
        t.y += swap_a.y * swap_b.m;
        t.x += swap_b.x * swap_a.m;
        t.y += swap_b.y * swap_a.m;
        t.x /= t.m;
        t.y /= t.m;
        t.vz = Math.sqrt(t.x*t.x + t.y*t.y);
        return t;
        }

app.func.lopatkaVahaSwap = function(a, b)
        {
        var tmp;
        tmp = a.m;
        a.m = b.m;
        b.m = tmp;
        }

app.func.cycle = function (arr, func)
        {
        var i, i_max;
        l = arr.length
        i_max = l * 31;
        for (i=0;i<i_max; i++)
                {
                a = Math.floor(Math.random() * l);
                b = Math.floor(Math.random() * l);
                if (a==b)
                        {continue;}
                func(arr[a], arr[b]);
                }
        return;
        }

app.func.sortCmpShuffle2 = function(a, b)       // DESC b,a
        {
//      if (!(0.66-Math.random()<=0))
//              {
                app.func.lopatkaVahaSwap(a, b);
//              return -1;
//              }
//      return -1;
        }

app.func.sort3Cmp = function(a, b)
        {
        var t1, t2;
        if (a.x==b.x && a.y==b.y)
                {return 0;}
        t1 = app.vars.tez;
        t2 = app.func.telesoTezisteSwap(t1, a, b);
        if (!(t1.vz-t2.vz<=0))
                {
                app.func.lopatkaVahaSwap(a, b);
                app.vars.tez = t2;
//              return -1;      // -1 aby uz nevymenoval a, b
                }
//      return -1;
        }

// ----
        // program
        time_limit = 300; // 300 [ms]

        time = 0;
        PERF.getTime();
        for (i=0; i<10000 && time<time_limit; i++)
                {
                func.cycle(lop, func.sortCmpShuffle2);  // zamichej, serad random
                app.vars.tez = func.telesoTeziste(lop); // po zamichani je treba prepocitat teziste kvuli funkci 'sort3Cmp' + 'telesoTezisteSwap'
                func.cycle(lop, func.sort3Cmp); // optimalizuj
                func.cycle(lop, func.sort3Cmp); // optimalizuj
                func.saveBest(lop);
                time += PERF.getTime();
                }
        cycles = i;
Editováno 27. září 7:57
 
Nahoru Odpovědět
27. září 7:55
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:27. září 8:20

Mimochodem, na tech grafech jsem si vsiml, ze ty nejvetsi hodnoty jsou rovnomerne do trojuhelniku. To by mohlo vylepsit optimalizer. Pripadne uz na zacatku to rozhazovat trojuhelnikove.
A tez by slo udelat to, ze kdyz se vysledky dlouho nemeni, zastavit cyklus.

 
Nahoru Odpovědět
27. září 8:20
Avatar
mifro
Člen
Avatar
Odpovídá na Peter Mlich
mifro:28. září 10:10

Jak to na tom odkazu spustím? Zkoušel jsem různé prohlížeče, ale nic...

 
Nahoru Odpovědět
28. září 10:10
Avatar
mifro
Člen
Avatar
Odpovídá na Peter Mlich
mifro:28. září 11:04

Aha, tak ve FF to jede ok. Je nějaký způsob, jak to převést do VB?
Zkoušel jsem výsledky zadat do programu (algo Bugmaster) k porovnání a vypadá to taky perfektně.

 
Nahoru Odpovědět
28. září 11:04
Avatar
mifro
Člen
Avatar
Odpovídá na Bugmaster
mifro:28. září 16:32

vývažek počítám takto (měl jsem v excelu)
spočtu RAD lopatky (=PI()/180*úhel)
Xn = sin(RAD) x hmotnost lopatky
Yn = cos(RAD) x hmotnost lopatky
součet hodnot Xn je hmotnost vývažku
pak (ARCTG2 součtu hodnot Yn / 180) / PI je úhel vývažku

 
Nahoru Odpovědět
28. září 16:32
Avatar
mifro
Člen
Avatar
mifro:28. září 17:24

Ještě jedna věc - šel by do grafu vložit bod, který by znázornil umístění vývažku? Tzn. tam např. vykreslit červený bod na vypočteném úhlu. Příklad v příloze.

 
Nahoru Odpovědět
28. září 17:24
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:30. září 8:26

Aha.
vyvazek = vektor teziste * prumerna hmotnost lopatky
poloha = [-tx, -ty] (symetricky k tezisti pres stred)

Polohu T tam zobrazuji na okraji na ramecku, protoze cisla vychazeji tam mala, ze by se kryla se stredem. Tak jsem to nazoomoval.
Mimo FF jsem to netestoval. Udelal jsem nejake upravy pro IE9, ale ten graf to tam zobrazuje nekde bokem, asi a taaak dlouho. Zajimavy je rozdil, Ie 100 cyklu, FF 2000 cyklu :) Jo, provedl jsem nejake nevyznamne zmeny, takovy pokus, kde je lepsi dat vic cyklu. Vyplatilo se mi to u michani.

for (i=0; i<20000 && time<time_limit; i++)
        {
        func.cycle(lop, func.cycleCmpShuffle, 22);      // zamichej, serad random
        app.vars.tez = func.telesoTeziste(lop);         // po zamichani je treba prepocitat teziste kvuli funkci 'sort3Cmp' + 'telesoTezisteSwap'
        func.cycle(lop, func.sort3Cmp, 11);             // optimalizuj
        func.saveBest(lop);
        time += PERF.getTime();
        }

VBA neumim. Umel bych to prepsat, ale nepotrebuji. Princip jsem popsal. Nahodne lopatky promicham A pak v cyklu nahodne vyberu 2 lopatky a zkusim je vymenit, zda se zlepsi teziste. Neco podobne dela Bugmaster. Jeho VBA kod jsem nezkoumal. Bugmaster jde na to mozna chytreji u te optimalizace, zkousi vymenu v nejakem konkretnim poradi. Rikam, nezkoumal jsem to. Jen jsem cetl popisek na foru, co napsal.

Editováno 30. září 8:27
 
Nahoru Odpovědět
30. září 8:26
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:30. září 8:51

Tak jsem to jeste upravil pro ten IE, i graf to zobrazuje. Problem byl, ze min/max se pocita v IE a FF odlisnym zapisem. A navic IE ten FF chape jako chybu syntaxe, musel jsem to ohranicit evalem. A taky jsem prepsal zobrazovani z innerHTML na appedChild. Takze se graf zobrazuje asi 200ms v IE misto 2s :) A pak jsem udelal zmeny ohledne zobrazovani vysledku pro IE, jeste.

 
Nahoru Odpovědět
30. září 8:51
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:30. září 13:29

A)
Jeste bych mel jeden tip, jak to delat.

  • seradis vahu DESC
  • vaha MIN
  • naplnis lopatky x, y, vahaMIN
  • pak projdes vsechny lopatky a kde vaha = vahaMIN, tam vlozis hmotnost[0], vypocitas teziste a ulozis nejlepsi moznost
  • vratis puvodni hmostnost, vyberes dalsi lopatku, vlozis tam hmotnost[0], teziste, ulozis nejlepsi
  • az projdes vsechny lopatky, ulozis hmotnost na to nejlepsi misto
  • vyberes hmotnost[1] a opet, zkusis ulozit na vsechny volne pozice, pocitas teziste...

B)
Mas 0 lopatek. Postupne pridavas dalsi a dalsi. Menis x,y podle poctu lopatek a snazis se vybrat polohu nove pozice pro novou hmotnost pro nejlepcejsi teziste.
Cili, vkladas lopatku nekde mezi uz hotove. V podstate je to algoritmus insert sortu.

1 - ulozis nejlepsi

(2) 1
1 (2) - ulozis nejlepsi

(3) 1 2
1 (3) 2
1 2 (3) - ulozis nejlepsi

Tim, ze jedes od nejtezsi, tak by ti mensi hmotnosti meli dovazovat zbytek.
Nevyhoda je, ze dostanes tu nejhorsi variantu zhlediska stability :) Hvezdici. Lopatky se ti rozhodi v takovemto trojuhelniku:
1-2-3-2-1 - 1-2-3-2-1 - 1-2-3-2-1

 
Nahoru Odpovědět
30. září 13:29
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:1. října 10:42

Tak, ten prvni algoritmus vypada asi takhle.
http://mlich.zam.slu.cz/…iste-alg.htm
Resil jsem to trochu jinak.

  • seradim vahy
  • naplnim vsechny lop. min vahou.
  • najdu prvni hodnotu min. vahy a dam misto ni nejvyssi vahu
  • pak volam v cyklu algoritmus pro posouvani vahy pres vsechny lopatky a prepocet teziste
  • a pak to cele opakuji pro vsechny vahy

Dava to dobre vysledky, ale to nahodne zamichani davalo lepsi. Nicmene, cas je 2ms. Mozna by to slo vyuzit misto nahodneho zamichani na zacatku tech predchozich algoritmu.

A myslim si, ze ted druhy algoritmus, B, by mel spocitat tu nulu jako ten excelovy resitel. Ale, jak rikam, predpokladam, ze rozmisteni vahy bude tvorit hvezdici a hvezdine je nestabilni. Staci malo a cele se to rozvibruje a bude problem to ustalit. Na druhu stranu, teziste nebude prilis poskakovat.

 
Nahoru Odpovědět
1. října 10:42
Avatar
mifro
Člen
Avatar
mifro:2. října 11:49

Díky moc všem za postřehy a rady. Vše si ještě podrobně projdu. Každopádně jste mi moc pomohli. Určitě vyplodím ještě nějaký dotaz :-D

 
Nahoru Odpovědět
2. října 11:49
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:4. listopadu 10:24

Jeste mam jeden algoritmus. Vychazi z toho, co jsem uz popsal.

  • seradim DESC
  • seradim 0, n, 1, n-1, 2, n-2 ... (na stridacku nejvetsi, nejmensi)
  • postupne vytvarim vetsi a vetsi kolo, prepocitavam polohu lopatek, hmotnost necham z predchoziho stavu
  • novou lopatku se snazim zamenit s kazdou predchozi, zda nebude lepsi teziste

Vytvari to takovy hvezdicovy system. Vetsi vahy vytvori treba trojuhelnik, mensi protitrouhelnik pro 6 lopatkach.
Mozna dobre jako prvotni nastrel nebo postup, kde neni nutny pocitac.
Zkousel jsem na to navazat nahodny vyber 2 lopatek a jejich zamena, ale lepsi je predtim nahodne promichani :)

10090
10020
10300
10030
10210
10080
10060
10070
10300
10100
10060
10090
10160
10100
10130
10130
10120
10120
({x:-0.0001086, y:0.000201, m:182170, vz:0.00022842600­831638631})
2.3118 -- hmotnost protivahy

https://mlich.zam.slu.cz/js-teziste.htm

 
Nahoru Odpovědět
4. listopadu 10:24
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:4. listopadu 10:38

pr.
1 2 3 11 12 13
13 12 11 3 2 1 - desc
13 1 12 2 11 3 - velke, male, to se z predchoziho serazeni od nejvetsiho vytvari dobre
A pak vytvarim kolo
13 - 1, dve lopatky, poloha pro dve lopatky
13 - 1 - 12, prepocitam polohu, zkusim 12 vymenit za 1, pak 12 za 13 a zjistim, ktere teziste je nej
13 - 1 - 12 - 2, prepocitam, vymenuji 2 za vsechny predesle
...
vytvori to prave polohy typu - hvezdici (2 trouhelniky), 2 ctverce, 2 petiuhelniky...
13 - 1 - 12 - 2
13 - 1 - 12 - 2 - 11 - 3

 
Nahoru Odpovědět
4. listopadu 10:38
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 93 zpráv z 93.