Naivni algoritem

[sabrinacalcina]

Pozdravljeni,

pri delu Naivnega algoritma sva naletela na težavo.

In sicer pri dokumentu prvi_del.ipynb pri inputu In [127]: Če sva število povezav in oglišč zamenjala na večja števila, nama programa ne dokonča. Npr.: [seznam_gra, utezi] = graf(20, 20, 100, 0, 10) . Prosila bi, če je mogoče da nama za te velike številke poženete, saj nama v online CoCalcu to ne uspe.

Poleg tega naju pri inputu In [122], zanima ali sva si to sploh prav zamislila, saj naju večinoma vrže kar na drugi else in s tem algoritem ne vrne nič novega. Vrne namreč enako kot pri zgornjem inputu In [126]. Le to pa je enako kot najmanjsi_xl = najmanjsi_x(x, vektor_xl) . To sicer načeloma ni narobe, vendar iz tega težko dobiva kakršne koli ugotovitve.

Prosila bi, če bi bilo možno, da pogledate algoritem razisci, ter nama poveste če je kdaj prišlo do print("Najdeno je bilo izboljšanje.") . Tako bi vedela, da najin algoritem vsaj približno deluje. ##

Lep pozdrav, Sabrina Calcina in Jan Črne

[jaanos]

Ideja funkcije razisci izgleda v skladu s tem, kar je opisano v članku. Seveda pa bo, ko velja x0 == x1, veljalo alfa_m == 0 in ato vek_zv == diag, do izboljšanja pa ne bo prišlo. Morda je problem že v tem, kako računata arglexmin. Dejansko bi ga lahko računala po definiciji leksikografske ureditve:

def arglexmin(seznam_x, vektorji):
    _, xmin = min(([numpy.dot(numpy.array(v), numpy.array(x)) for v in vektorji], x) for x in seznam_x)
    return xmin

najmanjsi_xl = arglexmin(x, [avr_pov, d])
najmanjsi_xr = arglexmin(x, [d, avr_pov])

Bi pa vseeno opozoril na to, da seznam uer definirata izven funkcije razisci, kar pomeni, da se bodo rešitve iz predhodnih klicev ohranjale (morda je to sicer smiselno, če želita imeti možnost prekinitve brez izgube vmesnih rezultatov). Pazita tudi na vračanje v primeru, ko najdeta izboljšanje - and je logični operator, tako da bo v tem primeru odgovor True ali False. Morda bo bolje, če enostavno izvedeta oba rekurzivna klica vsakega v svoji vrstici, nato pa prepustita vračanje zadnji vrstici funkcije.

Bom pognal še In [127], pa odprem pull request z izhodom.

[sabrinacalcina]

Pozdravljeni, popravila sva predlagane funkcije, poleg tega sva uporabila vašo funkcijo arglexmin. Sedaj upava, da algoritem dela. Prosila bi vas, če lahko poženete v inputu In 116 in sicer za večje številke, kot na primer [seznam_gra, utezi] = graf(20, 30, 200, 0, 10). Ter na slednjemu najin algoritem def razisci3. Zanima naju če v kakšnem primeru algoritem vrne kakršnokoli izboljšanje.

Lep pozdrav, Sabrina Calcina in Jan Črne

[sabrinacalcina]

Pozdravljeni, v grid_grafi.ipynb nama funkcijarazišči, kar je v članku poimenovano naivni algoritem, ne vrača pametnih rezultatov, kljub temu da sva funkcijo še dodelala na izboljšanih grafih, ter se nama zdi ideja pravilna. Včasih se zgodi, da rekurzija predolgo traja in ne veva kje v sami rekurziji je problem. V pripravi na izboljšan algoritem, pa se nama zalomi ker ne veva kako speljati rekurzije. OBJ2 po enem krogu je že zelo velik in ne veva ali je to narobe. Prosiva za pomoč.

Lp, Sabrina Calcina in Jan Črne