ในทฤษฎีความซับซ้อนของการคำนวณปัญหาการค้นหาเชิงเส้นเป็นปัญหาการค้นหาที่เหมาะสมที่สุดซึ่งนำเสนอโดยRichard E. Bellman ^{[ 1 ]}และได้รับการพิจารณาโดยอิสระโดยAnatole Beck ^{[ 2 ] [ 3 ] [ 4 ]}

"ผู้ซ่อนตัวซึ่งอยู่กับที่นั้นตั้งอยู่บนเส้นจำนวนจริงตามการกระจายความน่าจะเป็น ที่ทราบ แล้ว ผู้ค้นหาซึ่งมีความเร็วสูงสุดเท่ากับหนึ่ง เริ่มต้นจากจุดกำเนิดและต้องการค้นหาผู้ซ่อนตัวให้ได้ในเวลาที่คาดการณ์น้อยที่สุด สมมติว่าผู้ค้นหาสามารถเปลี่ยนทิศทางการเคลื่อนที่ได้โดยไม่เสียเวลา และสมมติว่าผู้ค้นหาไม่สามารถมองเห็นผู้ซ่อนตัวได้จนกว่าจะถึงจุดที่ผู้ซ่อนตัวอยู่จริง ๆ และเวลาที่ผ่านไปจนถึงขณะนั้นคือระยะเวลาของเกม"

ปัญหาคือการหาผู้ซ่อนตัวให้เจอในเวลาที่สั้นที่สุดเท่าที่จะเป็นไปได้ โดยทั่วไป เนื่องจากผู้ซ่อนตัวอาจอยู่ด้านใดด้านหนึ่งของผู้ค้นหาและอยู่ห่างออกไปในระยะทางใดๆ ผู้ค้นหาจึงต้องเคลื่อนที่ไปมา กล่าวคือ ผู้ค้นหาต้องเคลื่อนที่ไปเป็นระยะทาง x1 _ในทิศทางหนึ่ง กลับไปยังจุดเริ่มต้น และเคลื่อนที่ไปเป็นระยะทาง x2 _ในอีกทิศทางหนึ่ง เป็นต้น (โดยความยาวของขั้นตอนที่ n จะถูกแทนด้วย xn ₎ (อย่างไรก็ตาม วิธีแก้ปัญหาที่ดีที่สุดไม่จำเป็นต้องมีขั้นตอนแรก และอาจเริ่มต้นด้วยการ "เคลื่อนที่" เล็กๆ จำนวนอนันต์ครั้ง) ปัญหานี้มักเรียกว่าปัญหาการค้นหาเชิงเส้น และแผนการค้นหาเรียกว่าวิถีการเคลื่อนที่

ปัญหาการค้นหาเชิงเส้นสำหรับการกระจายความน่าจะเป็นทั่วไปยังไม่ได้รับการแก้ไข^{[ 5 ]}อย่างไรก็ตาม มี อัลกอริทึม การเขียนโปรแกรมแบบไดนามิกที่สร้างวิธีแก้ปัญหาสำหรับการกระจายแบบไม่ต่อเนื่องใดๆ^{[ 6 ]}และยังมีวิธีแก้ปัญหาโดยประมาณสำหรับการกระจายความน่าจะเป็นใดๆ ด้วยความแม่นยำที่ต้องการ^{[ 7 ]}

ปัญหาการค้นหาเชิงเส้นได้รับการแก้ไขโดย Anatole Beck และDonald J. Newman (1970) ในรูป แบบเกมผลรวมเป็นศูนย์สำหรับผู้เล่นสองคน วิถีการเคลื่อนที่ แบบมินิแม็กซ์ของพวกเขาคือการเพิ่มระยะทางเป็นสองเท่าในแต่ละขั้นตอน และกลยุทธ์ที่เหมาะสมที่สุดคือการผสมผสานของวิถีการเคลื่อนที่ที่เพิ่มระยะทางด้วยค่าคงที่ที่กำหนดไว้^{[ 8 ]}วิธีแก้ปัญหานี้ให้กลยุทธ์การค้นหาที่ไม่ไวต่อสมมติฐานเกี่ยวกับการกระจายของเป้าหมาย ดังนั้นจึงนำเสนอขอบเขตบนสำหรับสถานการณ์ที่เลวร้ายที่สุด วิธีแก้ปัญหานี้ได้รับในกรอบของอัลกอริทึมออนไลน์โดยShmuel Galซึ่งได้ขยายผลลัพธ์นี้ไปยังชุดของรังสีที่ขนานกันด้วย^{[ 9 ]}อัตราส่วนการแข่งขันออนไลน์ที่ดีที่สุดสำหรับการค้นหาบนเส้นตรงคือ 9 แต่สามารถลดลงเหลือ 4.6 ได้โดยใช้กลยุทธ์แบบสุ่ม Demaine et al. ได้ให้วิธีแก้ปัญหาออนไลน์ที่มีต้นทุนต่อรอบ^{[ 10 ]}

ผลลัพธ์เหล่านี้ถูกค้นพบอีกครั้งในช่วงทศวรรษ 1990 โดยนักวิทยาศาสตร์คอมพิวเตอร์ในชื่อปัญหาเส้นทางเดินของวัว (cow path problem )

• การค้นหาเชิงเส้น
• ค้นหาเกม