최단 경로 그래프 순회에서 Dijkstra, Bellman-Ford 및 Floyd의 알고리즘의 성능을 비교하기 위해 큰 (아래에 자세히 참조) 임의 그래프를 만들어야합니다. 인접성을 배열에 저장하고 있습니다. 지금까지 정점 사이에 임의의 가중치를 생성하고 주 대각선을 0으로 채웠습니다. 나는 또한 주 대각선에 대해 대칭을 가지고 있습니다 (그래프가 방향이 없지만 반드시 완전히 연결되어 있지는 않다고 가정하고 있습니다).
임의 값은를 사용하여 생성 된 0-24 ish 범위에 rand() % 25있습니다. 문제는 그래프가 더 희박 해지기를 원한다는 것입니다 (즉, 가장자리가 적음). 범위 내에서 난수를 생성하고 생성 된 숫자의 약 1/3에서 1/2이 특정 값이되도록하는 방법이 있습니까? 무작위 분포는 내가하는 일에 그다지 중요하지 않습니다.
또 다른 질문 : 성능 차이를 확인하기 위해 얼마나 큰 그래프를 테스트해야합니까? 정점 10 개? 100? 1000? 10000000?
C ++는 원하는 것을 달성 하는 discrete_distribution및 uniform_int_distribution클래스를 제공합니다 . 예는 다음과 같습니다.
#include <random>
#include <iostream>
template<typename rgen>
int custom_random_int(rgen& mt) {
// Returns 0 at a 1/3 chance, 1 at a 2/3 chance
std::discrete_distribution<> d({1, 2});
// Uniform distribution of integers in [0, 24]
std::uniform_int_distribution<> ud(0, 24);
if (d(mt) == 0) {
// Return 0 at 1/3 chance
return 0;
} else {
// Output a random number at 2/3 chance
return ud(mt);
}
}
int main() {
// Fixed seed of 1 for demonstration purposes
std::seed_seq ss{ 1 };
std::mt19937 mt(ss);
for(int i = 0; i < 100; i++) {
std::cout << custom_random_int(mt) << std::endl;
}
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다