np-hard

0열

1답변

그래서 여행자가 그래프에서 특정 거리를 여행 할 수 있고 모든 양방향 가장자리가 길이 (거리)가있는 문제를 발견했습니다. 특정 가장자리 (어느 방향)를 여행 할 때 여행 할 수있는 주어진 거리에 대해 수집 할 수있는 최대 금액을 찾아야하므로 돈/선물 (모든 가장자리에 문제가 있음)이 표시된다고 가정하십시오. 기본적인 문제는 주어진 거리 (그래프에 루프가있을

1열

3답변

왜 정점 채색은 NP 어려운가요?

버텍스 컬러링 알고리즘을 읽고 있습니다. 문제가 O (| V | + | E |)에서 풀릴 수 있음을 암시하는 BFS를 사용하여 문제를 해결할 수있는 방법을 설명하는 문서를 볼 수 있습니다. 그러나이 또한 NP 어려운 문제라고 언급 한 것을 볼 수 있습니다. ?이 두 가지가 함께 맞는 어떻게 당신은 어떤 빛을 던져 주시겠습니까 여기 는 나에게 일반적인 경우

0열

1답변

차량 하나만 사용하여 VRPTW에서 주행 거리를 최적화 할 수 있습니까?

하나의 차량 만 사용하여 VRPTW를 최적화 할 수 있습니까? 단일 차량은 고객의 약속 시간 순서대로 고객에게 가야하기 때문에.

1열

1답변

NP-complete 대 NP-hard (이유가 동일하지 않은 이유)

NP- 하드가 NP 완성과 다른 이유는 무엇입니까? 정의의 내 비공식적 인 이해는 사용 : NP를 - NP-완전한 다항식 시간에 검증 할 수있는 모든 문제 - NP와 NP-어려운 모든 문제를 NP 하드 - 적어도 NP에서 가장 어려운 문제만큼 어렵습니다. 의사 결정 문제 - 입력과 관련하여 질문을하고 bool 값을 출력하는 문제 혼란 : NP 우리가 증명

3열

1답변

NP- 완료의 복잡도 측정

예를 들어, 세트 - 커버 결정 문제는 NP 완전 문제로 알려져 있습니다. 이 문제의 입력은 우주 U, U의 부분 집합의 가족 S 및 정수 k()입니다. 내가 혼란스러워하는 한 가지는 k = 1이라고하면, S의 각 요소를 간단히 검사하여 시간 | S |에서 문제를 풀 수 있다는 것입니다. 일반적으로 k가 상수 일 때 , 문제는 | S |의 다항식 시간으로

1열

2답변

일부 NP-Complete 문제는 어떻게 NP-Hard가 될 수 있습니까?

나는 P, NP, NP-Complete 및 NP-Hard를 직관적 인 방식으로 랩핑하려고 노력하고있어 그 정의를 기억할 필요가 없습니다. 다음 이미지 (왼쪽 시나리오, P! = NP)에는 NP-Complete와 NP-Hard 사이에 겹치는 영역이 있습니다. 일부 문제는 NP-Complete 및 NP-Hard라는 것을 의미합니까? 나는이 모순 된 대답을 발견

0열

1답변

균일 성 제한이없는 하이퍼 그래프의 꼭지점 채색은 NP-hard입니까?

균일 성 제한이없는 하이퍼 그래프의 꼭지점 색은 NP-hard입니까? k-unoform 하이퍼 그래프의 정점 색상 표시가 NP 하드임을 보여주는 논문을 보았습니다. 그러나 일반적인 경우 (k- 유니폼이 아닌) 하이퍼 그래프의 정점 색칠이 NP 하드인지 여부를 명시 적으로 나타내는 소스는 찾을 수 없습니다.

0열

1답변

최적 경로 커버의 NP 완전성 증명.

이 paper은 블록 그래프 또는 2 부분 순열 그래프의 최적 경로 커버 문제를 해결합니다. 소개의 세 번째 줄에서는 최적의 경로 커버 문제는 NP-Complete이며 "컴퓨터 및 다루기 힘든 부분 : David S. Johnson, Michael R. Garey의 NP 완전성 이론 안내서"를 참조했습니다. 그러나 나는 그 책에서 그 증거를 찾을 수 없었다

0열

2답변

N 개의 양수 중에서 크기 1에서 L까지의 가장 큰 분리되고 연속적인 부분 집합을 반환하십시오.

Maximizing the overall sum of K disjoint and contiguous subsets of size L among N positive numbers에 제공된 Paul Hankin 알고리즘을 일반 크기로 만들려고합니다. 솔루션은 정확히 크기 L 인 각 부분 집합에만 국한되지 않으며 목표는 전체 합계를 최대화하는 것이 아니라 최대한

0열

1답변

색도에 대한 빠른 정확도 해석기

그래프의 반음계 수를 찾는 것은 NP 하드 문제이므로 '이론적으로는'빠른 솔버가 없습니다. 그래프의 정확한 반음계 수를 신속하게 계산할 수있는 공개적으로 사용 가능한 소프트웨어가 있습니까? 많은 그래프의 반음계를 계산하는 Python 스크립트를 작성하고 있지만 작은 그래프의 경우에도 너무 오래 걸립니다. 그래프 나는 스파 스 또는 밀도가 있지만 일반적으로