Temat: Jaki algorytm rozwiązuje układ równań liniowych o...
Kamil Bęczyński:
Cześć, czy znacie jakiś algorytm który rozwiązuje układ równań liniowych o tylko binarnych zmiennych ? Przy czym układ
Z tego co pisałeś to rozumiem, że wynik ma być całkowito-liczbowy.
równań może nie być pełny, ale nie jest sprzeczny. Wydaje mi
Jak ustaliłeś, że nie jest sprzeczny?
się, że problem jest bardziej skomplikowany, niż modyfikacja algorytmy eliminacji gaussowskiej polegająca na dodaniu rozbijania danego równania układu na k równań w przypadku, gdy równanie to ma k zmiennych i ich suma wynosi k.
Każdy solver do problemu programowania całkowito-liczbowego jest w stanie poradzić sobie z takim zadaniem. Przynajmniej teoretycznie.
To czego szukasz to rozwiązania dopuszczalnego. Aby to uzyskać w funkcji celu wystarczy wpisać 0.
Spójrz też na to:
http://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_e...
Jeśli są to zmienne o wartościach ze zbioru {0,1} to być może podejście oparte na programowaniu w logice z więzami byłoby dobre.
Co do proponowanego algorytmu genetycznego to nie widzę sensu stosowania do takiego problemu. Co więcej za mało wiadomo o problemie bo może być tak, że klasyczny AG może kompletnie nie poradzić sobie, np. jak obszar dopuszczalny nie jest jednospójny.
пропозиції роботи
