431 Graphs + Planning

What is a planning problem, and how is its state space formally represented as a graph structure?

• Planning Problem: Finding an optimal sequence of actions to reach a goal state from an initial state under resource constraints.

• Graph Representation: Nodes = world states; Directed Edges = valid actions transitioning between states.

What key challenges complicate real-world planning problems, and how do AI methods address them?

• Challenges: Massive search spaces, chains of interdependent decisions, strict constraints (deadlines/capacity), and real-world uncertainties.

• AI Solution: Systematically explores alternative action sequences, optimizes trade-offs, and adapts plans dynamically.

What is the Bin Packing Problem, and what operational constraint distinguishes online bin packing from offline bin packing?

• Bin Packing: Packing varying-sized items into the minimal number of fixed-capacity bins without overloading any bin or splitting items.

• Online vs. Offline: Online receives items sequentially with no future knowledge and permanent placement; offline knows all items and sizes upfront.

What are the computational complexity classes of bin packing, and why do we rely on approximation heuristics?

• Complexity: Offline optimization is NP-hard (decision version is NP-complete); online has no universally optimal algorithm.

• Why Heuristics: Exact solutions are too slow for large inputs, so fast heuristics provide guaranteed upper bounds on bin counts.

How do Next-Fit, First-Fit, and Best-Fit select bins for arriving items, and what are their running times and performance bounds?

• Next-Fit (NF): Checks current bin only; opens new bin if it doesn't fit. O(n) time | Max 2 * OPT bins.

• First-Fit (FF): Places item in earliest-opened bin with space. O(n^2) time | Max 1.7 * OPT bins.

• Best-Fit (BF): Places item in bin with tightest fit (highest current load). O(n^2) time | Max 1.7 * OPT bins.

What preprocessing step converts First-Fit into First-Fit Decreasing (FFD), in what problem type is it used, and why does it work?

• Preprocessing: Sorts items from largest to smallest before running First-Fit.

• Problem Type: Offline only (requires knowing all sizes in advance).

• Why it Outperforms Online Rules: Placing large items first prevents them from being blocked by small items placed early.

What is Resource Allocation in Container-based Clouds (RAC), and how is its problem structure formally classified in bin packing terminology?

• RAC Definition: Distributing container workloads across virtual and physical servers to minimize resource usage and power consumption.

• Problem Classification: A two-level, two-dimensional vector bin packing problem.

  • Two Levels: Containers pack into Virtual Machines (VMs), and VMs pack into Physical Machines (PMs).

  • Two Dimensions: Must satisfy both CPU and Memory capacity bounds simultaneously at each level.

How do the required allocation decisions differ between homogeneous and heterogeneous cloud data centers, and what capacity constraints apply?

• Homogeneous Decisions (3): Which existing VM, which VM type to create, and which PM to host it.

• Heterogeneous Decisions (4): Adds a 4th decision choice: which PM type to create.

• Constraints: Every container gets exactly 1 VM; every VM gets exactly 1 PM; total CPU and Memory demands must never exceed host capacity at either level.

What operational distinction separates static RAC from dynamic RAC, and what three sequential decision stages are executed for an arriving container in dynamic allocation?

• Static vs. Dynamic: Static knows all workloads upfront (uses offline search like GAs); dynamic receives containers sequentially with no future knowledge (uses immediate online heuristics).

• Three Dynamic Decisions: (1) VM Selection (existing VM), (2) VM Creation (new VM type), and (3) PM Selection (hosting PM).

How do Dual-Chromosome GA and Group Genetic Algorithm (GGA) differ in representing cloud allocations, and why does GGA perform better?

• Dual-Chromosome GA: Uses an indirect representation that requires an arbitrary decoding heuristic (like Next-Fit) to construct actual allocations.

• GGA: Uses a direct grouped representation (containers inside VMs, VMs inside PMs).

• Why GGA Wins: Dual-Chromosome solution quality is limited by its lossy decoding heuristic, whereas GGA directly mutates and evolves real allocation groups.

What are the specific mechanisms and purposes of Gene-Level Crossover and Rearrangement in Group Genetic Algorithms?

• Gene-Level Crossover: Sorts PMs by utilization, copies highly-utilized PM structures directly from parents to offspring, and collects remaining unallocated items as free containers.

  • Purpose: Preserves good PM configurations.

• Rearrangement: Replaces two small containers in a VM with a candidate free container, then re-packs the displaced small containers using First-Fit.

  • Purpose: Inserts free containers and optimizes VM space utilization.

What are the specific mechanisms and purposes of the Unpack and Merge operators in Group Genetic Algorithms?

• Unpack: Assigns probabilities inverse to PM utilization and dismantles under-utilized PMs so their containers can be reallocated.

  • Purpose: Eliminates low-utilization PMs.

• Merge: Replaces multiple smaller VM instances on a PM with a single larger VM instance.

  • Purpose: Introduces new VM types and optimizes PM utilization.

How do the GGA operators collaborate during the evolutionary search process?

• Gene-Level Crossover + Rearrangement: Preserves good PMs and optimizes VM utilization.

• Unpack + Rearrangement: Optimizes VM utilization by dismantling weak PMs and re-packing their containers into open VM gaps.

• Merge + Other Operators: Introduces new VM types and optimizes PM utilization by consolidating small VMs into larger ones.

How are graph search problems formally structured, and how do adjacency matrices compare to adjacency lists in space and lookup efficiency?

• Formal Search Components: Initial state S0, state transition relation R, and goal acceptance criterion A(S).

• Adjacency Matrix:

  • Uses Theta(n^2) space; edge existence lookup takes Theta(1) time; neighbor listing takes Theta(n) time.

    • Best for dense graphs.

• Adjacency List:

  • Uses Theta(n + e) space; edge existence lookup takes Theta(n) time worst-case; neighbor listing takes Theta(1) time per neighbor.

    • Best for sparse graphs.

How do connectivity definitions differ between undirected and directed graphs?

• Undirected Connectivity: A path exists between every pair of nodes u and v.

• Directed Strong Connectivity: A directed path exists from u to v AND from v to u for every pair of nodes.

What three structural properties define the Tree Triad Theorem for an undirected graph with n nodes?

• (1) The graph is connected.

• (2) The graph contains no cycles.

• (3) The graph contains exactly n - 1 edges. (Note: Any 2 conditions automatically prove the 3rd).

How are game states and transitions represented in a graph search framework, and why is the Game of Nim graph strictly acyclic?

• Graph Representation: Nodes represent game configurations, and directed edges represent legal moves.

• Acyclic Reason: Moves strictly decrease the total match count, making it physically impossible to return to any prior state.

What formal decision rules determine whether a game state configuration is classified as winning or losing under optimal play?

• Winning State: Has at least one successor state that is losing for the opponent.

• Losing State: Has all successor states leading to winning positions for the opponent.

How does the choice of frontier data structure dictate graph search behavior?

• Frontier Data Structure: A Queue (FIFO) produces Breadth-First Search (BFS), a Stack (LIFO) produces Depth-First Search (DFS), and a Priority Queue produces Best-First Search.

What structural edge properties differentiate BFS trees from DFS trees?

• (Quick Context: A tree edge is an edge used to discover a brand-new node. A non-tree edge is a leftover edge from the original graph that was skipped because the node on the other end was already visited.)

  • BFS Trees (Horizontal Rule): Non-tree edges only connect nodes in the same layer or adjacent layers (layer index difference $\le 1$).

    • They never jump across multiple layers.

  • DFS Trees (Vertical Rule): Non-tree edges only connect nodes vertically along the exact same branch (connecting a node directly back to an ancestor or down to a descendant).

    • They never jump horizontally across separate branches.

What are the asymptotic time complexities of Breadth-First Search and Depth-First Search, and how is this complexity proven?

• Time Complexity: Both BFS and DFS run in Theta(n + e) time on a graph with n nodes and e edges.

• Proof Mechanics: Every node is visited exactly once, and every edge is traversed/encountered at most twice (totaling at most 2e + n operations).

How is an implicit search graph defined, and what trade-offs govern visited-state tracking during search?

• Implicit Definition: Defined by a root state s and a successor function f(u) that generates adjacent states on the fly: G = (s, f).

• Option 1: Ignore

  • Lots of redundant searching, or getting stuck in cycles.

• Option 2: Keep path so far, and check if node on path

  • Solves cycles, but still does redundant searching

• Option 3: Keep and check set of visited states

  • Potentially requires O(n) space

Why do traditional tree-based Genetic Programming methods struggle with web service composition, and how does the GraphEvol framework overcome this limitation?

• Tree GP Limitation: Struggles to guarantee functional correctness (frequently generates invalid connections between mismatched service input/output data types).

• GraphEvol Solution: Models workflows directly as directed data-flow graphs and uses a constructive graph-building algorithm that strictly checks and enforces valid data connections at every step.

How does the GraphEvol framework evaluate and optimize composite web service workflows during evolutionary search?

• Evolutionary Operators: Uses graph crossover (merging two parent workflow graphs) and graph mutation.

• Fitness Formula: Evaluates solutions using Fitness = w1 * (1 / Longest_Path_Length) + w2 * (1 / Total_Services), where w1 + w2 = 1.

• Optimization Goal: Simultaneously minimizes execution latency (longest start-to-end path) and workflow complexity (total number of atomic services).

What is the fundamental difference between algorithm complexity and problem complexity?

• Algorithm Complexity: The running time of one specific implementation or algorithm (e.g., MergeSort runs in Θ(n log n)).

• Problem Complexity: The inherent computational difficulty of the underlying problem itself—defined as the lower bound runtime of the most efficient algorithm possible.

How does a binary decision tree mathematically prove the Ω(n log n) lower bound for comparison sorting?

• Sorting n items requires distinguishing between n! possible sorted permutations (leaves of the decision tree).

• A binary tree with n! leaves must have a height of at least log2(n!) = Θ(n log n). Thus, no comparison-based sort can run faster than Ω(n log n) in the worst case.

What is a model of computation, and why are Class P and Class NP defined around YES/NO decision problems?

• Model of Computation: A formal mathematical framework (like a Turing Machine) defining how inputs are processed into outputs using state rules and memory.

• Decision Focus: Turing Machines process inputs and halt in an Accept (YES) or Reject (NO) state.

  • Because P and NP are defined via Turing Machines, they are fundamentally classes of YES/NO decision problems.

What does the polynomial reduction formula A ≤_P B mean, and how do you read its direction?

• Meaning (A ≤_P B): Problem A can be re-formatted/transformed into Problem B in polynomial time.

• Direction: Read ≤_P as "easier than or equal to in difficulty". A is on the left (easier/known), and B is on the right (harder/target). Problem B is at least as hard as Problem A.

How does a Non-Deterministic Turing Machine (NTM) define Class NP, and what is the equivalent DTM verification property?

• NTM: A theoretical machine that branches non-deterministically at each step, evaluating all execution paths in parallel (or using an "oracle" to guess valid choices).

• Class NP: Decision problems solvable by an NTM in polynomial time, which is mathematically equivalent to candidate solutions (certificates) being verifiable in polynomial time on a standard Deterministic Turing Machine (DTM).

What criteria define NP-Complete (NPC) vs. NP-Hard, and what two steps prove a new problem X is NPC?

• NP-Complete (NPC): Must satisfy BOTH:

  • (1) Belongs to NP (YES/NO decision problem verifiable in polynomial time), AND (2) Is NP-Hard (B ≤_P A for all B ∈ NP).

• NP-Hard: Every problem in NP reduces to it (B ≤_P A), but it does NOT need to belong to NP (can be search/optimization problems returning numbers).

• Two Steps to Prove X is NPC:

  1. Prove X ∈ NP (candidate solutions are verifiable in polynomial time).

  2. Pick a known NPC problem Y and prove Y ≤_P X.

How does the Cargo Truck (Bin Packing) scenario distinguish between P, NP, NP-Complete (NPC), and NP-Hard?

• Class P (Easy to Solve): "What is the total weight of 10 boxes?" $\rightarrow$ Solvable in fast O(n) polynomial time.

• Class NP (Easy to Check): "Can these boxes fit into these 3 specific trucks?" $\rightarrow$ Hard to solve from scratch, but checking a given packing list takes seconds.

• Class NP-Complete / NPC (Hardest YES/NO): "Can 100 boxes fit into at most 5 trucks?" $\rightarrow$ A YES/NO decision question in NP, but sits at the maximum difficulty ceiling of NP.

• Class NP-Hard (Optimization): "What is the absolute MINIMUM number of trucks needed?" $\rightarrow$ At least as hard as NPC, but outputs an exact optimal number rather than a YES/NO answer.