Backtracking: N Bishops Problem - algoritmus

Tento problém ma blázni ... Niesť biskupov na doske NxN takým spôsobom, kde by všetky štvorce boli obsadené alebo napadnuté aspoň jedným z nich.

Mohol by mi niekto pomôcť s algoritmom na vyriešenie tohto problému?

odpovede:

Prečo sa vrátiť späť? Na získanie dôkazu použite malý počet riešení.

Dokonca aj chamtivý algoritmus postačí: Počítejte počet štvorcov, ktoré sa dajú dostať z každého štvorca. Vyberte najvhodnejší štvorec, ktorý sa neprekrýva s predtým vybraným dosahom. Opakujte.

Nesprávnosť generuje horizontálne, vertikálne a stredové variácie.

N biskupov je dostatočný len na to, aby sa dostali na každé námesties presne jedným biskupom. Ak ste vybrali štvorce s prekrývajúcim sa dosahom, konečná zhoda dosiahnuteľných štvorcov by bola nižšia. Hmm, možno je potrebné kvantifikovať, koľko nižšie pre akýkoľvek zlý štvorec. Znie to možné.

Pre takýto obrovský problémový priestor nie je búrlivá sila spätná väzba sľubná.

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Existuje minimálne a maximálne riešenie tohto problému, nie je to triviálne.

Skontroluj to BishopsProblem alebo viac detailné

Som si istý, že ľahko nájdete príklad v c.

Predpokladám, že požadujete nejaké optimalizácie, pretože algoritmus spätného odklonu je taký, aký je.

Prvá vec, ktorú si všimnete, je, že môžete oddeliť čierne a biele - zoberiete súčet B_i * W_j kde i + j = N, Uhlopriečky môžete tiež zobraziť akojednoduchá mriežka (s obmedzeniami), pretože to pravdepodobne spôsobí, že kód bude prísnejší a možno ľahšie pochopiteľný. Ďalšia optimalizácia si všimne, že farba nemusí nutne záležať - výsledky pre niektorých černochov môžu byť použité pre niektoré biele. a keď to nie je.

Dúfam, že je to dosť dobrý nárast - mal by byť dostatočný pre niektoré menšie N.