여기 이 문제 풀수있는사람 있냐?
익명(112.149)
2014-01-29 12:02
추천 0
댓글 39
다른 게시글
-
컹커러가 다 좋은데TheProdigy(theprodigy) | 14.01.29추천 0
-
프로그램 시써봤음 ㅎㅎ [4]서정코더(221.161) | 14.01.29추천 1
-
4년제 대졸 출신 경력 4년차 최종연봉 2400 [2]ㅁㄹ(14.36) | 14.01.29추천 0
-
있잖아.....1(220.92) | 14.01.29추천 0
-
it 대기업 노리는데말이야... [3]1(220.92) | 14.01.29추천 0
-
컴공은 1억이상 받으려면 사업밖에 없냐? [1]익명(223.62) | 14.01.29추천 0
-
어셈으로 CPU마비 가능? [6]고정닉없다..(rollrat) | 14.01.29추천 0
-
C언어 질문입니다. [5]알려주세요(211.201) | 14.01.29추천 0
-
안녕 뉴비임니헵(hep93) | 14.01.29추천 0
-
학원 고졸 출신 경력 3년차 이직 현재연봉 3500 [7]플밍(115.143) | 14.01.29추천 0
프로그램 돌리셈.
허접한 solver 만들어서 돌리면 안풀린다는 소문이 있던데??
Solver가 다거기서 거기지. 그러면 무작위 방식으로 코딩해보셈. 이건 안뚫리는게 없음. 아니면 1부터 9까지 첫칸부터 박으면서 무한박하든가. 하면 될듯
영어 못 읽어서 이해불가..
휴리스틱이네. 내가 제일 좋아하는 분야이면서 대학원 박사 전공으로 연구하려고 하는 분야지.
sosintegral 님이 이런 것도 만들었었던게 생각나는군.
http://sos440.tistory.com/381
다항 복잡도 알고리즘따위 없는 NP 최적화 휴리스틱이야말로 인간이 신을 가장 가깝게 흉내낼 수 있는 예술
굿인데. 사이트에 들어가서 자동 풀이 실행해보면 이 알고리즘으로 풀 수 없는 문제라고 나오는 것들도 있는데 이건 뭐야?? 문제 마다 알고리즘을 계속 새로 만들어줘야 되는건가??
휴리스틱으로 풀 필요는 없는듯. 명확히 룰이 있는 수도쿠 문제는 더욱. 더군다나 빨리 푸는게 관건인데 타임컴플렉스가 복잡한 휴리스틱이 웬말임?
룰대로 풀면서(셀 &줄에 1~9가 하나씩 있어야함) 나머진 백트레킹으로 풀어도 금방 나올듯.
스도쿠가 명확한 룰이 있긴 한데... 비어있는칸이 많으면 못푸는 문제도 있고 푸는데 엄청 오래걸리는 문제도 있는거 같은데? 휴리스틱이 뭔지는 모르겠지만 이런 이유 때문에 쓰는거 같은데...
ㅇㅇ // 완벽하게 모든 스도쿠를 풀 수 있는 알고리즘은 없으니깐. P = NP 라고 증명된다고 해도(그럴리 없지만) 막상 발견하려면 오래 걸릴거고.
낙타 // 먼 개소리냐 넌
휴리스틱이 별게 아니고 어떤 문제를 해결하는 데에 있어서 인간이 머릿속으로 푸는 어떤 기교를 흉내낸 것부터 시작한 알고리즘(지금은 그렇게 단순한 건 아니지만) 그래서인지 휴리스틱 로직을 보면 논리적으로 깔끔하다는 느낌이 아니라 더럽다는 느낌부터 들지.
class. 스도쿠릉 완벽하게 풀수있는 알고리즘이 왜 없냐?
직접 스도쿠를 짜보지는 않았지만. 내가볼땐 위 문제의 경우엔 백트랙킹으로 충분히 가능할듯 하다.
가장 간단한 예로 TSP 를 들면 제일 먼저 누구나 가장 간단하게 생각해내는 건 도시를 방문하는 모든 경로를 체크하는 거지만 이 경우 복잡도는 사실상 n=50만 되도 거의 풀기 어려워지지만 휴리스틱으로 최적화를 하지.(그래봐야 크게 줄어들진 않지만)
낙타 // 그러니까 니가 직접짜보라고 입 그만털고 새키야
난 점심먹으러 간다 ㅅㄱ
클래. 인공지능 같은 휴리스틱은 경우의 수(시공간복잡도)가 너무 큰 경우. 시간내에 정확한 해를 찾을수 없어서 근접해를 찾기 위함 인데. 스도쿠가 근접해를 찾는것도 아니고 답을 찾는건데 왜 쓰냐고. 답 틀려도 대충 찾는다는거냐? 말도 안되는 소리하네. 위 문제 경우는 시간 복잡도가 크지도 않는데. 백트래킹으로 풀몈 더 정확하고 빠른데 휴리스틱을 왜 쓰냐고 병신아. 대학원 진로로 생각한다는거 보니까.. 그냥 휴리스틱 홀릭에 빠져서 무조건 들이대네 ㅋㅋㅋ 구구단 짜는데 휴리스틱 쓸래? /찾아보니 대부분 백트래킹으로 풀었구만.
위 사이트에서 문제나 제대로 읽어보고 밀하는건지 모르겠네.
여러분 제가 병신입니다. 그만 싸우셈. ----끝----
근데 위키에서 sudoku 보면, The general problem of solving Sudoku puzzles is known to be NP-complete. 라고 나오는데 문제가 중간 정도 되면 백트래킹으로 풀리고 그거 보다 어려우면 백트래킹으로 푸는데 오래걸리지 싶은데...
일반적인 경우라면 np로 보는게 맞겠지만. 위 경우 사이트에 간단한 경우의 스도쿠 50문제라고 되어있음. 답이 딱 한가지만 존재하는 문제들이라고.
A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction. The 6K
집앞 슈퍼가는데 가차타고 갈판.
간단한 경우라고 어디 써있음? contains fifty different Su Doku puzzles ranging in difficulty 이렇게 되있는데... 50가지 여러 난이도의 퍼즐인데...
문제를 자기 맘대로 간단하게 해석하넴...
신기하네요
영어를 가르쳐야 하는건가...? 답이 유니크한 범위 내에서의 난이도가 여러가지라고 되어 있는데요? 위에서 보여준 예제는 한번에 다이렉트로 풀수있는 케이스고. 그보다 복잡해도 답이 유니크한 범위.
A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this) 이거 읽을줄 알면. 내말 알게 됨. ㅇㅇ
ㅉㅉ 답이 당연히 유니크 해야지 여러개면 답을 어떻게 내서 제출함?? 답이 유니크 하면 무조껀 쉬운 문제임? 스도쿠 자체가 NP 문제라는데 답이 유니크 하면 NP 가 아닌문제임?? 말이 되는 소릴 해야지...
NP-C 문제임. 그냥 NP 가 아니라. ㅡㅡ.
NP-C 문제는 NP 문제가 아님??
http://algospot.com/judge/problem/read/TSP3
이거 어떻게 품?
참치 // 아까 위에서 내가 말한 대로임
참치 // 구XX 님(저 문제 내신 분)이 쓰신 그 유명한 책에 보면 TSP 의 단계별 최적화(가면 갈수록 더 빠르게 최적화함) 과정 4개인가 5개였나 나와있음.
참치 // 일종의 그런 휴리스틱 최적화로 푸는 문제임. 꼭 책에 나와있는 거 말고도 수많은 휴리스틱이 알려져있는데 뭐 책에 나온건 사실 비교적 간단한 거지만 저 문제 푸는데엔 충분함.
http://en.m.wikipedia.org/wiki/Sudoku_solving_algorithms
ㅇㅇ. 그냥 np가 아니라고 했지 언제 Np 가 아니라고 함? npc 는 np 부분집합임 ㅡㅡ.
위에 위키나 보삼.