探索アルゴリズムの概要と各種アルゴリズムおよび実装

import heapq

def dijkstra(graph, start):
    # 各ノードへの最短距離を無限大に初期化
    distances = {node: float('infinity') for node in graph}
    # 出発地点への距離は0に設定
    distances[start] = 0
    # ノードのキューを作成し、出発地点を追加
    priority_queue = [(0, start)]

    while priority_queue:
        # 最も距離が短いノードを選択
        current_distance, current_node = heapq.heappop(priority_queue)

        # より短い経路が見つかった場合、無視する
        if current_distance > distances[current_node]:
            continue

        # 隣接ノードを探索
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            # より短い経路が見つかった場合、距離を更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 例として、グラフを作成
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# 出発地点から各ノードへの最短距離を計算
start_node = 'A'
shortest_distances = dijkstra(graph, start_node)
print(shortest_distances)

import heapq

def heuristic(node, goal):
    # ヒューリスティック関数（ヒューリスティック推定値）を定義
    # ここではユークリッド距離を使用
    x1, y1 = node
    x2, y2 = goal
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def astar(graph, start, goal):
    open_set = [(0, start)]
    came_from = {}
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while open_set:
        current_f, current_node = heapq.heappop(open_set)

        if current_node == goal:
            path = []
            while current_node in came_from:
                path.append(current_node)
                current_node = came_from[current_node]
            path.append(start)
            path.reverse()
            return path

        for neighbor in graph[current_node]:
            tentative_g = g_score[current_node] + graph[current_node][neighbor]

            if tentative_g < g_score[neighbor]:
                came_from[neighbor] = current_node
                g_score[neighbor] = tentative_g
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score[neighbor], neighbor))

    return None

# 例として、2次元グリッド上の経路探索を行う
graph = {
    (0, 0): {(0, 1): 1, (1, 0): 1},
    (0, 1): {(0, 0): 1, (1, 1): 1},
    (1, 0): {(0, 0): 1, (1, 1): 1},
    (1, 1): {(0, 1): 1, (1, 0): 1}
}

start_node = (0, 0)
goal_node = (1, 1)
path = astar(graph, start_node, goal_node)
print(path)

import random

# 例として、生産ジョブのリストを生成
jobs = [
    {'id': 1, 'processing_time': 4},
    {'id': 2, 'processing_time': 3},
    {'id': 3, 'processing_time': 2},
    {'id': 4, 'processing_time': 6},
    {'id': 5, 'processing_time': 5}
]

# 遺伝子表現: ジョブの順序
def generate_individual():
    return random.sample(jobs, len(jobs))

# 評価関数: 生産スケジュールの評価（目的関数）
def evaluate(individual):
    total_processing_time = 0
    total_completion_time = 0
    for job in individual:
        total_processing_time += job['processing_time']
        total_completion_time += total_processing_time
    return total_completion_time

# 選択操作: トーナメント選択
def select(population, tournament_size):
    tournament = random.sample(population, tournament_size)
    return min(tournament, key=lambda x: evaluate(x))

# 交叉操作: 順序交叉 (OX)
def crossover(parent1, parent2):
    n = len(parent1)
    start = random.randint(0, n - 1)
    end = random.randint(start, n)
    child = [None] * n

    for i in range(start, end):
        child[i] = parent1[i]

    remaining = [job for job in parent2 if job not in child]
    j = 0
    for i in range(n):
        if child[i] is None:
            child[i] = remaining[j]
            j += 1

    return child

# 突然変異操作: ジョブの位置をランダムに交換
def mutate(individual):
    n = len(individual)
    i, j = random.sample(range(n), 2)
    individual[i], individual[j] = individual[j], individual[i]

# 遺伝的アルゴリズムの実行
population_size = 50
tournament_size = 5
mutation_probability = 0.2
generations = 100

population = [generate_individual() for _ in range(population_size)]

for _ in range(generations):
    new_population = []
    for _ in range(population_size):
        parent1 = select(population, tournament_size)
        parent2 = select(population, tournament_size)
        child = crossover(parent1, parent2)
        if random.random() < mutation_probability:
            mutate(child)
        new_population.append(child)
    population = new_population

# 最適な生産スケジュールを見つける
best_schedule = min(population, key=lambda x: evaluate(x))
best_completion_time = evaluate(best_schedule)

print("最適な生産スケジュール:", [job['id'] for job in best_schedule])
print("最適な完了時間:", best_completion_time)