zadatschitsch

[C'Tebo]

______123___71___150___27
_58____a_____b____c_____d
126____e_____f____g_____h
_28____i______j____k_____l
159____m_____n___o_____p

Evo ovo treba riješit. Gore i ljevo su rezultati zbroja (dakle: a+b+c+d=58, a+e+i+m=123 i tako dalje)
Ali rezultati moraju biti cijeli brojevi između 0 i 255.

Kako se inače rješavaju ovakvi zada(t)ci?


Ako ovoj temi nije mjesto ovdje, samo vi prebacite negdje drugdje, meni je jedino ovdje palo na pamet to postat.

_________________
Click me!
_______________________
Bad panda!

[vsego]

Nemam blage kako i zasto, ali meni je u prvom pokusaju "na srecu" uspjelo:

[krcko]

Ajoj. Cjelobrojno rjesavanje linearnih jednadzbi uz uvjete tipa 0<x<255 moglo bi biti tezak problem, pache NP-potpun (nisam siguran). Znam da je cjelobrojno linearno programiranje NP-potpuno, a za rjesavanje jednadzbi trazite Dujinu ekspertizu (ako je bitno).

No u ovom konkretnom primjeru radi se o problemu diskretne tomografije. To je ono na cemu se bazira ultrazvuk, razni CT-ovi i slicno. Treba rekonstruirati matricu na temelju suma redaka i stupaca. U pravoj (kontinuiranoj) tomografiji rekonstruira se slika na temelju "linijskih integrala". Recimo da si olaksamo zivot i trazimo da varijable budu samo nule ili jedinice (umjesto cijeli brojevi izmedju 0 i 255). Onda su poznati nuzni i dovoljni uvjeti na sume da bi rjesenje postojalo (Gale-Ryserov teorem) i nacin da od jednog rjesenja napravimo sva ostala (Ryserov teorem). Ako nekog zanima predlazem da predjemo s time na "Kombinatoriku", jer rezultati imaju jak kombinatoricki flavour.

_________________
Vedran Krcadinac

Ljudi su razliciti, a nula je paran broj.

[C'Tebo]

Ajde de, onda (nisam basch puno pokoptscho schta si htio retcshi, al' ajde)

_________________
Click me!
_______________________
Bad panda!

[vsego]

[duje]

Ovaj puta nemam "ekspertizu", ali imam
jedno skoro trivijalno rjesenje.

Kao sto je Vsego primjetio, imamo 8 jednadzbi,
a 16 nepoznanica. No, zapravo imamo samo sedam
linearno nezavisnih jednadzbi, buduci zbroj svih
brojeva u matrici po retcima mora biti jednak
zbroju po stupcima. Stoga se cini da bi trebalo
postojati rjesenje samo 9 nula. I stvarno postoji.

Oznacimo zadane sume redaka sa a1, a2, a3, a4;
sume stupaca sa b1, b2, b3, b4; a trazene brojeve sa
sa x11, x12, ..., x44 (to su brojevi a, b, ..., p).
Na dijagonalu, na mjesto xii stavimo manji (ili jednak)
od brojeva ai, bi. Tada se polazni problem sveo na novi
u kojem su pripadne sume redaka i stupaca
ili 0 ili ai - bi ili bi - ai. U nasem konkretnom slucaju,
nove sume redaka su: 0, 55, 0, 132; a stupaca: 65, 0, 122, 0.
Opcenito, mogu nastupiti samo dvije mogucnosti:

1) medju sumama stupaca (ili redaka) su 3 nule. Tada sume
redaka (odnosno stupaca) stavimo u odgovarajuci ne-nul stupac
(odnosno) redak, a sve ostalo popunimo nulama.

2) medju sumama stupaca i medju sumama redaka su tocno dvije
nule (kao u nasem slucaju). No, tada se problem sveo na analogni
problem samo s matricom 2*2 (a ne 4*4), pa ga rijesimo na isti
nacin. U nasem primjeru, trebamo rijesiti problem u kojem su
sume redaka 55, 132, a stupaca 65, 122. Stavimo na dijagonalu
brojeve 55 i 122, te dobijemo problem sa sumama redaka 0, 10,
a stupaca 10, 0. Ovaj zadnji problem ima trivijano rjesenje:
stavimo 10 u donji lijevi kut. Stoga je jedno rjesenje predzanjeg
problema: prvi redak: 55 0, drugi redak 10, 122.

Konacno dobivamo jedno rjesenje polaznog problema: