FractalProjects의 다른 게임들

게임 정보

Npc Problems: Vertex Coloring은 실제 컴퓨터 과학 문제를 다루는 미니멀리즘 퍼즐 게임입니다.

• 독특한 방식의 퍼즐 게임.
  
• 인공지능만이 해결할 수 있는 문제.
  
• Npc 문제인 정점 색칠(Vertex Coloring)의 수작업으로 제작된 사례들을 해결해 보세요.
  
• 네온 그래픽과 오리지널 신스웨이브 음악이 어우러진 편안한 환경을 즐겨보세요.

연결된 원은 같은 색을 가질 수 없습니다. 최소한의 색상을 사용하여 모든 원을 칠할 수 있을까요?


추가 정보:
정점 색칠 문제는 노드와 선으로 이루어진 그래프로 표현됩니다. 정점을 연결하는 선을 간선(Edge)이라고 합니다.

정점 색칠 문제는 다항 시간 내에 풀 수 없는 NP-완전(NP-complete) 문제 중 하나입니다. 이러한 문제는 오늘날의 컴퓨터로도 해결하기 어려우며, 문제의 규모에 따라 해결책을 찾는 데 수년이 걸릴 수도 있습니다. 대규모 사례를 해결하려면 머신러닝과 인공지능의 활용이 필수적입니다. 이 게임에서는 플레이어가 직접 해결해 볼 수 있도록 비교적 작은 규모의 사례들이 제시됩니다.

정점 색칠 문제는 현실 세계에서 다음과 같이 다양하게 활용됩니다:

1) 일정 또는 시간표 작성: 대학 시험 일정을 만든다고 가정해 봅시다. 과목 목록과 각 과목을 수강하는 학생 명단이 있습니다. 많은 과목에 공통으로 수강하는 학생이 있을 것입니다(같은 학년, 재수강생 등). 공통 학생이 있는 두 시험이 같은 시간에 겹치지 않게 하려면 어떻게 일정을 짜야 할까요? 모든 시험을 치르기 위해 필요한 최소 시간 슬롯은 몇 개일까요? 이 문제는 각 정점이 과목이고, 두 정점 사이의 간선이 공통 학생의 존재를 의미하는 그래프로 표현할 수 있습니다. 즉, 최소 시간 슬롯의 수는 그래프의 색수(Chromatic number)와 같은 그래프 색칠 문제입니다.

2) 모바일 무선 주파수 할당: 타워에 주파수를 할당할 때, 같은 위치에 있는 모든 타워에는 서로 다른 주파수를 할당해야 합니다. 이러한 제약 조건 하에서 어떻게 주파수를 할당할까요? 필요한 최소 주파수 개수는 얼마일까요? 이 문제 역시 각 타워를 정점으로, 서로 범위 내에 있는 두 타워를 간선으로 연결하는 그래프 색칠 문제의 사례입니다.

3) 스도쿠: 스도쿠 또한 그래프 색칠 문제의 변형으로, 각 칸이 정점이 됩니다. 같은 행, 열, 또는 블록에 있는 두 정점 사이에는 간선이 존재합니다.

4) 지도 색칠: 국가나 주의 지도를 그릴 때 인접한 두 지역은 같은 색을 가질 수 없습니다. 어떤 지도든 4가지 색상만 있으면 충분히 칠할 수 있습니다.

출처: