[일반] 소코반 최적의 알고리즘 존재함?

[익명(118.235)]

해결가능한 임의의 소코반에 대하여

최소이동횟수 해결 알고리즘이 항상존재함?

(최소이동횟수가 몇인지 판별하는 알고리즘 혹은

최소이동횟수경로자체를 제시하는알고리즘)

아니면 일일이 노가다로 어떤게최소일지 확인하는수밖에없음?

이런류는 ㅇㅅㅇ

- dc official App

[익명(121.166)]

노가다도 알고리즘이야 완전탐색이라는 이쁜 이름이 있어요

[익명(118.235)]

노가다가 최적의알고리즘인지궁금해서 - dc App

[익명(118.235)]

최악의경우에도 N번의시도로 해결가능!같은 알고리즘 - dc App

[익명(121.166)]

보통 저런거는 A*알고리즘 같은거로 상태공간을 휴리스틱하게 탐색하지 deterministric하게 complexity를 결정하긴 좀 힘들어보이긴하는데

[익명(121.166)]

나무위키에서 슈퍼마리오가 NP컴플리트라고 본거같긴한데 ㅋㅋ

[익명(121.166)]

NP하드였네 8퀸은 NP컴플리트라고 함

[웨리(223.39)]

애초에 해결 가능한지 아닌지 판별하는 것부터 시작을 해야 얘기가 될 것 같은데 아닌가? - dc App

[웨리(223.39)]

그냥 어려워서 아무 말 던지고 가봄 - dc App

[익명(118.235)]

a* 알고리즘을 검색해보자