グラフ理論における極大および最大クリークの探索アルゴリズム
グラフ理論において、クリーク（clique）とは、頂点集合のうち、任意の2頂点間に辺が存在する部分グラフを指します。言い換えると、その集合内のすべての頂点が互いに隣接している完全なサブグラフです。
基本概念の整理
クリーク：頂点集合 \(C \subseteq V\) で、\(\forall u,v \in C,\ (u,v) \in E\) を満たすもの。
極大クリーク（maximal clique）：自身を真部 ...
6月27日 16:33 投稿
十字形グリッドにおける数値配置の全探索と制約検証
問題概要
特定形状を持つ 10 マスの格子（図参照）に、0 から 9 の各数字を重複なく 1 つずつ配置する必要があります。配置には以下の制約が課されます。
上下左右および斜め方向のどちらでも、隣り合うマスの数字の絶対値の差が「1」であってはならない。
┌─┬─┬─┐
│0│1│2│
├─┼─┼─┼─┤
│3│4│5│6│7│
├─┼─┼─┤
│ │ │
└─┴─┴─┘
8│9│
※位置インデックス ...
6月6日 17:44 投稿
AtCoder Beginner Contest 310 各問題のアルゴリズム解説とC++実装例
A: 別の注文方法
料理とセットで購入する場合、特定のドリンクが定価 \(P\) から割引価格 \(Q\) へ変更される。セット購入しない場合は、別のドリンクリストから任意の価格のものを選ぶことができる。支払い額を最小化する問題である。
実装方針は単純である。セット割引適用時の支払い額 \(Q + \min(A)\) と、割引なしの定価 \(P\) を比較し、小さい方を出力すればよい。\ ...
5月22日 01:48 投稿
Juliaによるバックトラッキングアルゴリズムの実装例
バックトラッキングアルゴリズムは、組み合わせ最適化問題を解決するための基本的な手法です。Julia言語を活用することで、明確で効率的な実装が可能です。以下、具体的な問題例を通じて実装方法を解説します。function solve_queens(n::Int)
board = zeros(Int, n, n)
solutions = Vector{Matrix{Int}}()
place_queens(board, 1, n, solutions)
return so ...
5月16日 13:35 投稿